Метод Ньютона (метод касательных). Решение систем нелинейных алгебраических уравнений

Читинский Государственный Университет

Энергетический институт

Факультет экономики и информатики

Кафедра прикладной информатики и математики

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Реферат

по дисциплине: Численные методы

на тему: Метод Ньютона (метод касательных). Решение систем нелинейных алгебраических уравнений.

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнила: ст. гр. ПИ-07-1

Злова В.В.

Проверила: Плюснина Т.А.

 

 

 

 

 

 

Чита, 2009

 

Содержание

 

Введение

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня заданной нелинейной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных.

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

 

 

Метод Ньютона. Решение систем нелинейных алгебраических уравнений

2.1 Метод Ньютона

2.1.1 Геометрическая интерпретация метода Ньютона

Этот метод применяется, если уравнение f(x) = 0 имеет корень x Î [a;b], и выполняются условия:

1) функция y=f(x) определена и непрерывна при xÎ(- ¥; + ¥)

2) f(a)·f(b)<0 (функция принимает значения разных знаков на концах отрезка [a;b]);

3) производные f ¢(x) и f ²(x) сохраняют знак на отрезке [a;b] (т.е. функция f(x) либо возрастает, либо убывает на отрезке [a;b], сохраняя при этом направление выпуклости).

4) f ¢(x) ¹ 0 при xÎ[a;b]

Основная идея метода заключается в следующем: на отрезке [a;b] выбирается такое число x0, при котором f(x0) имеет тот же знак, что и f ²(x0), т. е. выполняется условие f(x0)·f ²(x)>0. Таким образом, выбирается точка с абсциссой x0, в которой касательная к кривой y=f(x) на отрезке [a;b] пересекает ось Ox. За точку x0 сначала удобно выбирать один из концов отрезка.

Пусть нам дана некоторая функция f(x) = 0 на отрезке [a,b]. Возможно 4 случая:

- f(a)-f(b) < 0; f ¢(x) > 0; f ²(x) > 0

- f(a)-f(b) < 0; f ¢(x) > 0; f ²(x) < 0

- f(a)-f(b) > 0; f ¢(x) < 0; f ²(x) > 0

- f(a)-f(b) >0; f ¢(x) < 0; f ²(x) < 0

Рассмотрим метод Ньютона на первом случае.

Пусть нам дана возрастающая функция y = f(x), непрерывная на отрезке [a;b], и имеющая f ¢(x) > 0 и  f ²(x) > 0. Уравнение касательной имеет вид: y-y0= f ¢(x0)·(x-x0). В качестве точки x0 выбираем точку B(b; f(b)). Проводим касательную к функции y = f(x) в точке B, и обозначаем точку пересечения касательной и оси Ox точкой x1. Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x1, получаем точку b1. Снова проводим касательную к функции y = f(x) в точке b1, и обозначаем точку пересечения касательной и оси Ox точкой x2. Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x2, получаем точку b2.

Первое приближение корня определяется по формуле: .

Второе приближение корня определяется по формуле: .

Таким образом, i-ое приближение корны определяется по формуле:

Вычисления ведутся до  тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства | xi-xi-1| < e.

2.1.2 Алгоритм решения задач с помощью метода Ньютона

- определяем интервал (если он не задан), которому будет принадлежать корень уравнения.  Сужение интервала можно производить методом половинного деления.

- находим f ¢(x) и f ²(x), причем f ¢(x) ¹ 0 при xÎ[a;b], f ¢(x) и f ²(x)  должны сохранять знак на отрезке [a;b]

- выбираем один из концов  отрезка [a,b] за x0, исходя из того, что должно выполняться следующее условие f(x0)·f ²(x0)>0.

- вычисляем  , пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства  | xi-xi-1| < e.

2.1.3 Примеры решения уравнений с помощью метода Ньютона

Рассмотрим применение метода Ньютона на примерах.

1) Пусть нам дана функция f(x) = sin2x-lnx, если 1,3<x<1,5. Необходимо найти корень уравнения с точностью до 0,0001.

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

x	f(x)
1,3	0,253137	-1,47029
1,5	-0,26435	-0,12004

Так как, при x = 1,5, то за x0, берем x = 1,5.

x	f(x)		xn-xn-1
1,5	-0,2643451	-2,64665166
1,40012093	-0,001798363	-2,59883069	-0,0998707
1,39942894	-0,0000001988	-2,59825545	-0,00059199
1,39942887	-0,00000000000000003	-2,59825539	-0,00000007
1,39942887

Так как , то на данном шаге можно остановится.

Ответ:

2) Решить уравнение с .

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

Построив графики функций и , определяем, что у решаемого уравнения имеется только один корень, который находится в интервале 0.4<x<0.6. На данном интервале действительно содержит корень уравнения, т.к.

Уточним значение корня с требуемой точностью, пользуясь методом Ньютона.

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

Для функции имеем:

 и - положительные во всей области определения функции. В качестве начального приближения необходимо выбрать правую границу интервала x0=0.4, для которой выполняется неравенство:

Результаты вычислений:

Номер итерации	x0	F(x0)	F'(x0)	R	xn-xn-1
0	0,6	1,107982086	9,615964	0,115223192
1	0,484777	0,083308362	8,257956	0,010088255	-0,115223
2	0,474689	0,000690164	8,153249	0,000084649	-0,010088
3	0,474604	0,000001368	8,152379	0,000000168	-0,000085

 

 

Так как, на третьем шаге , то дальнейшие итерации можно не производить.

Ответ:

2.2 Решение систем нелинейных алгебраических уравнений

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

Запишем систему n нелинейных уравнений с n неизвестными в общем виде:

Эту систему можно записать в компактной, операторной форме:

F(X) = 0, где

- вектор-функция

- вектор неизвестных

Решением системы называется набор значений , (вектор X*), при которых все функции fi равны 0.

Системы нелинейных уравнений могут иметь единственное решение, множество решений или вообще не иметь его. Поэтому численное решение СНУ проводят в два этапа:

1 этап – отделение решений.

2 этап – уточнение всех или только нужных решений.

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

Для реализации данного этапа используются графические или аналитические способы.

При аналитическом способе отделения корней используется следующая теорема: непрерывная строго монотонная функция имеет и притом единственный нуль на отрезке [a;b] тогда и только тогда, когда на его концах она принимает значения разных знаков.

Достаточным признаком монотонности функции f(x) на отрезке [a;b] является сохранение знака производной функции.

Графический способ отделения корней целесообразно использовать в том случае, когда имеется возможность построения графика функции у = f(x).

Наличие графика исходной функции дает непосредственное представление о количестве и расположении нулей функции, что позволяет определить промежутки, внутри которых содержится только один корень. Если построение графика функции у = f(x) вызывает затруднение, часто оказывается удобным преобразовать данное уравнение к эквивалентному виду f1(x)=f2(x) и построить графики функций у = f1(x)  и у = f2(x) Абсциссы точек пересечения этих графиков будут соответствовать значениям корней решаемого уравнения.

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

Для систем с большим числом неизвестных (n ³ 3) удовлетворительных общих методов определения области существования решения нет. Поэтому при решении СНУ эта область обычно определяется при анализе решаемой задачи, например, исходя из физического смысла неизвестных.

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

Отделение решений позволяет:

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

2) Проанализировать возможность применения выбранного метода решения СНУ в каждой области.

3) Выбрать начальное приближение решения x0 из области его существования, так что x0ÎD.

При отсутствии информации об области существования решения СНУ выбор начального приближения x0 проводиться методом проб и ошибок.

Методы уточнения решений СНУ.

Уточнение интересующего решения до требуемой точности ε производится итерационными методами.

Основные методы уточнения решений СНУ получены путем обобщения итерационных процессов, используемых при решении одного нелинейного уравнения.

2.2.1 Метод итераций

Как и в случае одного уравнения, метод простых итераций заключается в замене исходной системы уравнений эквивалентной системой X=Φ(X), где

 

 и построении итерационной  последовательности X(k+1) = Φ(X(k)), где k=1,2,3,… - номер итерации, которая при k→∞ сходится к точному решению.

В развернутом виде формула итерационного процесса (выражение для вычисления очередного k-го приближения решения) имеет вид:

,

Условие окончания расчета

δ≤ε,  где  ε  -  заданная точность решения;

или

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

 

Таким образом, для уточнения решения СНУ методом простых итераций нужно найти такое эквивалентное преобразование в X=Φ(X), чтобы в области существования решения выполнялись условия сходимости.

2.2.1.1 Пример решения системы уравнений с помощью метода итераций

Решить систему нелинейных уравнений с точностью до 0,003

Дана система нелинейных уравнений:

Перепишем данную систему в виде:

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

Из графика видим, что система имеет одно решение, заключенное в области D: 0<x<0.3;  -2.2<y<-1.8.