Что такое начальное приближение функции

В нашем случае, сравним приближение, полученное на третьем шаге с реальным ответом, посчитанном на калькуляторе:

Рисунок 5. Корень из 2, посчитанный на калькуляторе

.

Как видно, уже на третьем шаге мы получили погрешность меньше 0.000002.

Таким образом можно вычислить значение величины «корень квадратный из 2» с любой степенью точности. Этот замечательный метод был изобретен Ньютоном и позволяет находить корни очень сложных уравнений.

Метод Ньютона: приложение на С++

В данной статье мы автоматизируем процесс вычисления корней уравнений, написав консольное приложение на языке C++. Разрабатывать его мы будем в Visual C++ 2010 Express, это бесплатная и очень удобная среда разработки С++.

Для начала запустим Visual C++ 2010 Express. Появится стартовое окно программы. В левом углу нажмем «Создать проект».

Рис. 1. Начальная страница Visual C++ 2010 Express

В появившемся меню выберем «Консольное приложение Win32», введем имя приложение «Метод_Ньютона».

Рис. 2. Создание проекта

В появившемся окно жмем «Готово». Далее появится окно, содержащее текстовый редактор кода для файла Метод_Ньютона.cpp.

Рис. 3. Редактор кода

Далее приведен подробный листинг Метода Ньютона:

// Метод_Ньютона.cpp: определяет точку входа для консольного приложения

using namespace std;

float f(double x) //возвращает значение функции f(x) = x^2-2

float df(float x) //возвращает значение производной

float d2f(float x) // значение второй производной

int _tmain(int argc, _TCHAR* argv[])

int exit = 0, i=0;//переменные для выхода и цикла

double x0,xn;// вычисляемые приближения для корня

double a, b, eps;// границы отрезка и необходимая точность

cin>>a>>b; // вводим границы отрезка, на котором будем искать корень

cin>>eps; // вводим нужную точность вычислений

if (a > b) // если пользователь перепутал границы отрезка, меняем их местами

if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня

if (f(a)*d2f(a)>0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // считаем первое приближение

while(fabs(x0-xn) > eps) // пока не достигнем необходимой точности, будет продолжать вычислять

xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона

> while (exit!=1); // пока пользователь не ввел exit = 1

Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5.

Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку.

Рис. 4. Решение ошибки компиляции проекта

Мы будем искать корни у функции f(x) = x2-2.

Сначала проверим работу приложения на «неправильных» входных данных. На отрезке [3; 5] нет корней, наша программа должна выдать сообщение об ошибке.

У нас появилось окно приложения:

Рис. 5. Ввод входных данных

Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет.

Рис. 6. Ошибка «На этом отрезке корней нет!»

Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0».

Теперь проверим работу приложения на корректных входных данных. Введем отрезок [0; 2] и точность 0.0001.

Рис. 7. Вычисление корня с необходимой точностью

Как мы видим, необходимая точность была достигнута уже на 4-ой итерации.

Чтобы выйти из приложения, введем «Exit?» => 1.

Метод секущих

Чтобы избежать вычисления производной, метод Ньютона можно упростить, заменив производную на приближенное значение, вычисленное по двум предыдущим точкам:

/

Итерационный процесс имеет вид:

где .

Это двухшаговый итерационный процесс, поскольку использует для нахождения последующего приближения два предыдущих.

Порядок сходимости метода секущих ниже, чем у метода касательных и равен в случае однократного корня .

Эта замечательная величина называется золотым сечением:

Убедимся в этом, считая для удобства, что .

Таким образом, с точностью до бесконечно малых более высокого порядка

Отбрасывая остаточный член, получаем рекуррентное соотношение, решение которого естественно искать в виде .

После подстановки имеем: и

Для сходимости необходимо, чтобы было положительным, поэтому .

Поскольку знание производной не требуется, то при том же объёме вычислений в методе секущих (несмотря на меньший порядок сходимости) можно добиться большей точности, чем в методе касательных.

Отметим, что вблизи корня приходится делить на малое число, и это приводит к потере точности (особенно в случае кратных корней), поэтому, выбрав относительно малое , выполняют вычисления до выполнения и продолжают их пока модуль разности соседних приближений убывает.

Как только начнется рост, вычисления прекращают и последнюю итерацию не используют.

Такая процедура определения момента окончания итераций называется приемом Гарвика.

Метод парабол

Рассмотрим трехшаговый метод, в котором приближение определяется по трем предыдущим точкам , и .

Для этого заменим, аналогично методу секущих, функцию интерполяционной параболой проходящей через точки , и .

В форме Ньютона она имеет вид:

Точка определяется как тот из корней этого полинома, который ближе по модулю к точке .

Порядок сходимости метода парабол выше, чем у метода секущих, но ниже, чем у метода Ньютона.

Важным отличием от ранее рассмотренных методов, является то обстоятельство, что даже если вещественна при вещественных и стартовые приближения выбраны вещественными, метод парабол может привести к комплексному корню исходной задачи.

Этот метод очень удобен для поиска корней многочленов высокой степени.

Метод простых итераций

Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки.

Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).

По теореме Банаха существует и единственна неподвижная точка

Она может быть найдена как предел простой итерационной процедуры

где начальное приближение — произвольная точка промежутка .

Если функция дифференцируема, то удобным критерием сжатия является число . Действительно, по теореме Лагранжа

Таким образом, если производная меньше единицы, то является сжатием.

Условие существенно, ибо если, например, на [0,1] , то неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины . Чем меньше , тем быстрее сходимость.

Рассмотрим уравнение: .

Если в качестве взять функцию , то соответствующая итерационная процедура будет иметь вид: . Как нетрудно убедиться, метод итераций в данном случае расходится при любой начальной точке , не совпадающей с собственно неподвижной точкой .

Однако можно в качестве можно взять, например, функцию . Соответствующая итерационная процедура имеет вид: .

Эти итерации сходятся к неподвижной точке для любого начального приближения :

Действительно, в первом случае , т.е. для выполнения условия необходимо чтобы , но тогда . Таким образом, отображение сжатием не является.

Рассмотрим , неподвижная точка та же самая, ситуация другая. Здесь, хотя формально производная может быть довольно большой (при малых ж), однако уже на следующем шаге она будет меньше 1.

т.е. такой итерационный процесс всегда сходится.

Метод Ньютона представляет собой частный случай метода простых итераций.

Здесь нетрудно убедиться, что при существует окрестность корня, в которой .

то если корень кратности , то в его окрестности и, следовательно,.

Если — простой корень, то сходимость метода касательных квадратичная (то есть порядок сходимости равен 2).

Поскольку , то

Таким образом, сходимость метода Ньютона очень быстрая.

Нахождение всех корней уравнения

Недостатком почти всех итерационных методов нахождения корней является то, что они при однократном применении позволяют найти лишь один корень функции, к тому же, мы не знаем какой именно.

Чтобы найти другие корни, можно было бы брать новые стартовые точки и применять метод вновь, но нет гарантии, что при этом итерации сойдутся к новому корню, а не к уже найденному, если вообще сойдутся.

Для поиска других корней используется метод удаления корней.

Пусть — корень функции , рассмотрим функцию. Точка будет являться корнем функции на единицу меньшей кратности, чем, при этом все остальные корни у функций и совпадают с учетом кратности.

Применяя тот или иной метод нахождения корней к функции , мы найдем новый корень (который может в случае кратных корней и совпадать с ). Далее можно рассмотреть функцию и искать корни у неё.

Повторяя указанную процедуру, можно найти все корни с учетом кратности.

Заметим, что когда мы производим деление на тот или иной корень , то в действительности мы делим лишь на найденное приближение , и, тем самым, несколько сдвигаем корни вспомогательной функции относительно истинных корней функции . Это может привести к значительным погрешностям, если процедура отделения применялась уже достаточное число раз.

Чтобы избежать этого, с помощью вспомогательных функций вычисляются лишь первые итерации, а окончательные проводятся по исходной функции , используя в качестве стартового приближения, последнюю итерацию, полученную по вспомогательной функции.

Мы рассмотрели решение уравнений только в одномерном случае, нахождение решений многомерных уравнений существенно более трудная задача.

Метод касательных

Метод касательных (метод Ньютона) предназначен для приближенного нахождения нулей функции, и сегодня мы не только узнаем его суть, но и научимся быстро решать тематическую задачу! В которой чаще всего фигурирует «обычная» функция одной переменной и соответствующее уравнение . Например:

Поставим задачу отыскать действительные корни данного уравнения.

А таковые точно есть! – из статей о графиках функций и уравнениях высшей математики вы хорошо знаете, что график функции-многочлена нечётной степени хотя бы один раз пересекает ось , следовательно, наше уравнение имеет по меньшей мере один действительный корень. Один. Или два. Или три.

Сначала напрашивается проверить, наличие рациональных корней. Согласно соответствующей теореме, на это «звание» могут претендовать лишь числа 1, –1, 3, –3, и прямой подстановкой легко убедиться, что ни одно из них «не подходит». Таким образом, остаются иррациональные значения. Иррациональный корень (корни) многочлена 3-й степени можно найти точно (выразить через радикалы) с помощью так называемых формул Кардано, однако этот метод достаточно громоздок. А для многочленов 5-й и бОльших степеней общего аналитического метода не существует вовсе, и, кроме того, на практике встречается множество других уравнений, в которых точные значения действительных корней получить невозможно (хотя они существуют).

Однако в прикладных (например, инженерных) задачах более чем допустимо использовать приближённые значения, вычисленные с определённой точностью.

Зададим для нашего примера точность . Что это значит? Это значит, что нам нужно отыскать ТАКОЕ приближённое значение корня (корней), в котором мы гарантированно ошибаемся, не более чем на 0,001 (одну тысячную).

Совершенно понятно, что решение нельзя начинать «наобум» и поэтому на первом шаге корни отделяют. Отделить корень – это значит найти достаточно малый (как правило, единичный) отрезок, которому этот корень принадлежит, и на котором нет других корней. Наиболее прост и доступен графический метод отделения корней. Построим поточечно график функции :

Из чертежа следует, что уравнение , судя по всему, имеет единственный действительный корень , принадлежащий отрезку . На концах данного промежутка функция принимает значения разных знаков: , и из факта непрерывности функции на отрезке сразу виден элементарный способ уточнения корня: делим промежуток пополам и выбираем тот отрезок, на концах которого функция принимает разные знаки. В данном случае это, очевидно, отрезок . Делим полученный промежуток пополам и снова выбираем «разнознаковый» отрезок. И так далее. Подобные последовательные действия называют итерациями. В данном случае их следует проводить до тех пор, пока длина отрезка не станет меньше удвоенной точности вычислений , и за приближённое значение корня следует выбрать середину последнего «разнознакового» отрезка.

Рассмотренная схема получила естественное название – метод половинного деления. И недостаток этого метода состоит в скорости. Медленно. Очень медленно. Слишком много итераций придётся совершить, прежде чем мы достигнем требуемой точности. С развитием вычислительной техники это, конечно, не проблема, но математика – на то и математика, чтобы искать наиболее рациональные пути решения.

И одним из более эффективных способов нахождения приближённого значения корня как раз и является метод касательных. Краткая геометрическая суть метода состоит в следующем: сначала с помощью специального критерия (о котором чуть позже) выбирается один из концов отрезка. Этот конец называют начальным приближением корня, в нашем примере: . Теперь проводим касательную к графику функции в точке с абсциссой (синяя точка и фиолетовая касательная):

Данная касательная пересекла ось абсцисс в жёлтой точке, и обратите внимание, что на первом шаге мы уже почти «попали в корень»! Это будет первое приближение корня . Далее опускаем жёлтый перпендикуляр к графику функции и «попадаем» в оранжевую точку. Через оранжевую точку снова проводим касательную, которая пересечёт ось ещё ближе к корню! И так далее. Нетрудно понять, что, используя метод касательных, мы приближаемся к цели семимильными шагами, и для достижения точности потребуется буквально несколько итераций.

Поскольку касательная определяется через производную функции, то этот урок попал в раздел «Производные» в качестве одного из её приложений. И, не вдаваясь в подробное теоретическое обоснование метода, я рассмотрю техническую сторону вопроса. На практике описанная выше задача встречается примерно в такой формулировке:

С помощью графического метода найти промежуток , на котором находится действительный корень уравнения . Пользуясь методом Ньютона, получить приближенное значение корня с точностью до 0,001

Перед вами «щадящая версия» задания, в которой сразу констатируется наличие единственного действительного корня.

Решение: на первом шаге следует отделить корень графически. Это можно сделать путём построения графика (см. иллюстрации выше), но такой подход обладает рядом недостатков. Во-первых, не факт, что график прост (мы же заранее не знаем), а программное обеспечение – оно далеко не всегда под рукой. И, во-вторых (следствие из 1-го), с немалой вероятностью получится даже не схематичный чертёж, а грубый рисунок, что, разумеется, не есть хорошо.

Ну а зачем нам лишние трудности? Представим уравнение в виде , АККУРАТНО построим графики и отметим на чертеже корень («иксовую» координату точки пересечения графиков):

Очевидное преимущество этого способа состоит в том, что графики данных функций строятся от руки значительно точнее и намного быстрее. Кстати, заметьте, что прямая пересекла кубическую параболу в единственной точке, а значит, предложенное уравнение и в самом деле имеет только один действительный корень. Доверяйте, но проверяйте 😉

Итак, наш «клиент» принадлежит отрезку и «на глазок» примерно равен 0,65-0,7.

На втором шаге нужно выбрать начальное приближение корня. Обычно это один из концов отрезка. Начальное приближение должно удовлетворять следующему условию:

Найдём первую и вторую производные функции :

и проверим левый конец отрезка:

Таким образом, ноль «не подошёл».

Проверяем правый конец отрезка:

– всё хорошо! В качестве начального приближения выбираем .

На третьем шаге нас ожидает дорога к корню. Каждое последующее приближение корня рассчитывается на основании предшествующих данных с помощью следующей рекуррентной формулы:

Процесс завершается при выполнении условия , где – заранее заданная точность вычислений. В результате за приближённое значение корня принимается «энное» приближение: .

На очереди рутинные расчёты:

(округление обычно проводят до 5-6 знаков после запятой)

Поскольку полученное значение больше , то переходим к 1-му приближению корня:

, поэтому возникает потребность перейти ко 2-му приближению:

Заходим на следующий круг:

, таким образом, итерации закончены, и в качестве приближённого значения корня следует взять 2-е приближение, которое в соответствии с заданной точностью нужно округлить до одной тысячной:

На практике результаты вычислений удобно заносить в таблицу, при этом, чтобы несколько сократить запись, дробь часто обозначают через :

Сами же вычисления по возможности лучше провести в Экселе – это намного удобнее и быстрее:

Ответ: с точностью до 0,001

Напоминаю, что эта фраза подразумевает тот факт, что мы ошиблись в оценке истинного значения корня не более чем на 0,001. Сомневающиеся могут взять в руки микрокалькулятор и ещё раз подставить приближенное значение 0,674 в левую часть уравнения .

А теперь «просканируем» правый столбец таблицы сверху вниз и обратим внимание, что значения неуклонно убывают по модулю. Этот эффект называют сходимостью метода, которая позволяет нам вычислить корень со сколь угодно высокой точностью. Но сходимость имеет место далеко не всегда – она обеспечивается рядом условий, о которых я умолчал. В частности, отрезок, на котором изолируется корень, должен быть достаточно мал – в противном случае значения будут меняться беспорядочным образом, и мы не сможем завершить алгоритм.

Что делать в таких случаях? Проверить выполнение указанных условий (см. выше по ссылке), и при необходимости уменьшить отрезок. Так, условно говоря, если бы в разобранном примере нам не подошёл промежуток , то следовало бы рассмотреть, например, отрезок . На практике мне такие случаи встречались, и этот приём реально помогает! То же самое нужно сделать, если оба конца «широкого» отрезка не удовлетворяют условию (т.е. ни один из них не годится на роль начального приближения).

Но обычно всё работает, как часы, хотя и не без подводных камней:

Определить графически количество действительных корней уравнения , отделить эти корни и применяя способ Ньютона, найти приближенные значения корней с точностью

Условие задачи заметно ужесточилось: во-первых, в нём содержится толстый намёк на то, что уравнение имеет не единственный корень, во-вторых, повысилось требование к точности, и, в-третьих, с графиком функции совладать значительно труднее.

А поэтому решение начинаем со спасительного трюка: представим уравнение в виде и изобразим графики :

Из чертежа следует, что наше уравнение имеет два действительных корня:

Алгоритм, как вы понимаете, нужно «провернуть» дважды. Но это ещё не самый тяжелый случай, бывает, исследовать приходится 3-4 корня.

1) С помощью критерия выясним, какой из концов отрезка выбрать в качестве начального приближения первого корня. Находим производные функции :

Тестируем левый конец отрезка:

Таким образом, – начальное приближение.

Уточнение корня проведем методом Ньютона, используя рекуррентную формулу:
– до тех пор, пока дробь по модулю не станет меньше требуемой точности:

И здесь слово «модуль» приобретает неиллюзорную важность, поскольку значения получаются отрицательными:

По этой же причине следует проявить повышенное внимание при переходе к каждому следующему приближению:

Несмотря на достаточно высокое требование к точности, процесс опять завершился на 2-м приближении: , следовательно:

с точностью до 0,0001

2) Найдем приближённое значение корня .

Проверяем на «вшивость» левый конец отрезка:

, следовательно, он не годится в качестве начального приближения.

«Прозваниваем» правый конец:

Таким образом: – начальное приближение.

Вычисления сведём в таблицу:

Здесь пришлось немножко постараться, правда, если выполнять вычисления в Экселе, то все «старания» займут доли секунды =)

, следовательно, итерации закончены:

Ответ: уравнение имеет два действительных корня: с точностью до 0,001

Парочка примеров для самостоятельного решения. И даже не столько для решения, сколько для отработки техники вычислений – сам-то алгоритм весьма примитивен:

Отделить действительный корень уравнения графически, и вычислить его приближенное значение методом касательных с точностью до 0,001

Определить количество действительных корней уравнения , отделить эти корни и применяя способ Ньютона, найти приближенные значения корней с точностью

Заметьте, что в последнем задании явно не указано, каким способом мы должны изолировать корни, и, в принципе, можно попробовать обойтись чисто аналитическими выкладками, за которые по идее не должны покарать. Другое дело, что графический метод почти всегда проще.

Пожалуй, основные практически важные моменты я раскрыл, а посему статья плавно перетекает в решения и ответы, где можно ознакомиться с примерными образцами чистового оформления рассмотренной задачи:

Пример 3 Решение: представим уравнение в виде и выполним чертёж:

Из чертежа следует, что
Уточнение корня проведем методом Ньютона, используя формулу:
, где – точность шага.
Начальное приближение должно удовлетворять условию .

Проверим левый конец отрезка:

, таким образом – начальное приближение.
Вычисления сведем в таблицу:

, следовательно, вычисления закончены.