Расчетная формула метода Ньютона имеет вид:

где n=0,1,2,..

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

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

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

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

Метода Ньютона (1) чувствителен к выбору начального приближения x 0 .

На практике для монотонной сходимости метода необходимо :

1-ая производная f(x)

2-ая производная f(x) должна быть знакопостоянна на интервале локализации [ a , b ] изолированного корня;

за начальное приближение x 0 выбирается та граница интервала локализации, на которой произведение функции на ее 2-ю производную больше нуля (f(c)f ’’ (c) > 0 , где с – одна из границ интервала) .

. При заданной точности >

Как указано в теореме, метод Ньютона обладает локальной сходимостью, то есть областью его сходимости является малая окрестность корня .

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

Метод простой итерации (метод последовательных повторений).

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

Это преобразование можно выполнить различными способами.

Функция называется итерационной функцией.

Расчетная формула метода простой итерации имеет вид:

где n=0,1,2,..

Теорема о сходимости метода простой итерации.

Пусть в некоторой - окрестности корняфункциянепрерывно дифференцируема и удовлетворяет неравенству

где 0 < q < 1 - постоянная.

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

со скоростью геометрической последовательности и справедлива оценка погрешности:

Критерий окончания итерационного процесса .

При заданной точности >0 вычисления следует вести до тех пор пока не окажется выполненным неравенство

Если величина , то можно использовать более простой критерий окончания итераций:

Если в неравенстве (5) q > 1 , то итерационный метод (4) расходится.

Если в неравенстве (5) q = 1 , то итерационный метод (4) может как сходится так и расходится.

В том случае, если q > = 1 , то итерационный метод (4) расходится и

применяется метод простой итерации с итерационным параметром .

Ключевой момент в применении состоит в эквивалентном преобразовании уравнения :

αf(x) = 0

x = x +αf(x) , (9)

где α – итерационный параметр (вещественная константа).

Расчетная формула метода простой итерации с итерационным параметром имеет вид:

x (n+1) = x (n) + αf(x (n) ) , (10)

где n=0,1,2,..

Итерационный процесс, построенный по форме (10) сходится , если:

1-ая производная функции f(x) знакопостоянна и ограничена на интервале локализации изолированного корня ;

знак итерационного параметра α противоположен знаку 1-ой производной функции f(x) на интервале локализации изолированного корня ;

модуль значения итерационного параметра α оценивается из неравенства

| α | < 2/M , (11)

где М – максимум модуля 1-ой производной функции f(x)

Тогда при таком выборе итерационного параметра  метод (10) сходится при любом значении начального приближения, принадлежащем интервалу , со скоростью геометрической прогрессии со знаменателем q равным

где m – минимум модуля 1-ой производной функции f(x) на интервале локализации изолированного корня .

Все люди от природы стремятся к знанию. (Аристотель. Метафизика)

Численные методы: решение нелинейных уравнений

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

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

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

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

В простейшем случае у нас имеется функция , заданная на отрезке (a , b ) и принимающая определенные значения.

Каждому значению x из этого отрезка мы можем сопоставить число , это и есть функциональная зависимость, ключевое понятие математики.

Нам нужно найти такое значение при котором такие называются корнями функции

Визуально нам нужно определить точку пересечения графика функции с осью абсцисс.

Метод деления пополам

Простейшим методом нахождения корней уравнения является метод деления пополам или дихотомия .

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

Алгоритм состоит в следующем.

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

Поделим отрезок пополам и введем среднюю точку .

Тогда либо , либо .

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

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

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

К достоинствам метода деления пополам следует отнести его высокую надежность и простоту.

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

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

Метод Ньютона: теоретические основы

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

Уравнение касательной к функции в точке имеет вид:

В уравнении касательной положим и .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

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

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

Упражнение 1 . Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

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

Визуализация метода Ньютона

Метод Ньютона (метод касательных) применяется в том случае, если уравнение f (x ) = 0 имеет корень , и выполняются условия:

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

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

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

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

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

Пусть нам дана возрастающая функция y = f(x) =x 2 -2, непрерывная на отрезке (0;2), и имеющая f " (x) = 2 x > 0 и f "" (x) = 2 > 0 .

Рисунок 1 . f(x) =x 2 -2

Уравнение касательной в общем виде имеет представление:

y-y 0 = f " (x 0)·(x-x 0).

В нашем случае: y-y 0 =2x 0 ·(x-x 0). В качестве точки x 0 выбираем точку B 1 (b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B 1 , и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

Рисунок 2. Результат первой итерации

y=f(x) Ox через точку x 1 , получаем точку В 2 =(1.5; 0.25) . Снова проводим касательную к функции y = f(x) в точке В 2 , и обозначаем точку пересечения касательной и оси Ox точкой x 2 .

Уравнение второй касательной: y -0.25=2*1.5(x -1.5), y = 3 x - 4.25.

Точка пересечения касательной и оси Ox: x 2 = .

Рисунок 3. Вторая итерация метода Ньютона

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку В 3 и так далее.

Рисунок 4. Третий шаг метода касательных

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

= 1.5.

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

=

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

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

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

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

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

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

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

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

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

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

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

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

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

// Метод_Ньютона.cpp: определяет точку входа для консольного приложения #include "stdafx.h" #include 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;// границы отрезка и необходимая точность cout<<"Please input \n=>"; cin>>a>>b; // вводим границы отрезка, на котором будем искать корень cout<<"\nPlease input epsilon\n=>"; cin>>eps; // вводим нужную точность вычислений if (a > b) // если пользователь перепутал границы отрезка, меняем их местами if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // считаем первое приближение cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // пока не достигнем необходимой точности, будет продолжать вычислять xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; } while (exit!=1); // пока пользователь не ввел exit = 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЛАБОРАТОРНАЯ РАБОТА №3-4.

Вариант №5.

Цель работы: научиться решать системы нелинейных уравнений (СНУ) методом простых итераций (МПИ) и методом Ньютона с помощью ЭВМ.

1. Изучить МПИ и метод Ньютона для решения систем нелинейных уравнений.

2. На конкретном примере усвоить порядок решения систем нелинейных уравнений МПИ и методом Ньютона с помощью ЭВМ.

3. Составить программу и с ее помощью решить систему уравнений с точностью .

ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ

Задание.

1. Аналитически решить СНУ:

2. Построить рабочие формулы МПИ и метода Ньютона для численного решения системы при начальном приближении: .

3. Составить программу на любом языке программирования, реализующую построенный итерационный процесс.

Решение.

Аналитический метод.

Аналитическим решением СНУ являются точки и .

Метод простых итераций (МПИ).

Для построения рабочих формул МПИ для численного решения системы необходимо вначале привести ее к виду:

Для этого умножим первое уравнение системы на неизвестную постоянную , второе - на , затем сложим их и добавим в обе части уравнения . Получим первое уравнение преобразуемой системы:

Неизвестные постоянные определим из достаточных условий сходимости итерационного процесса:

Запишем эти условия более подробно:

Полагая равными нулю выражения под знаком модуля, получим систему линейных алгебраических уравнений (СЛАУ) 4 порядка с 4 неизвестными :

Для решения системы необходимо вычислить частные производные :

Тогда СЛАУ запишется так:

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

Тогда СЛАУ запишется так:

Решением этой системы являются точки , , , . Тогда рабочие формулы МПИ для решения СНУ примут вид:

Для реализации на ЭВМ рабочие формулы можно переписать так:

Итерационный процесс можно начать, задав начальное приближение x 0 =-2, y 0 =-4. Процесс заканчивается при одновременном выполнении двух условий: и . В этом случае значения и являются приближенным значением одного из решений СНУ.

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

Для построения рабочих формул метода Ньютона в виде

где , необходимо:

1. Найти матрицу частных производных:

2. Найти определитель этой матрицы:

3. Определить обратную матрицу:

Проведя преобразования:

Получаем рабочую формулу метода Ньютона для реализации на ЭВМ:

Блок-схема МПИ и метода Ньютона для решения СНУ приведена на рисунке 1.

Рис.1 Схемы МПИ и метода Ньютона.

Тексты программ:

Program P3_4; {Iterations}

uses Crt;

var n: integer;

clrscr;

xn:=x-(x-y+2)+(1/2)*(x*y-3);

yn:=y+(2/3)*(x-y+2)+(1/6)*(x*y-3);

writeln (n:3, x:9:5, xn:9:5, (xn-x):9:5, y:9:5, yn:9:5, (yn-y):9:5);

n:=n+1;

until (abs(x-zx)<=eps) and (abs(y-zy)<=eps);

readln;

2) Метод Ньютона:

Program P3_4; {Nyuton}

uses Crt;

var n: integer;

x0,x,xn,y0,y,yn,eps,zx,zy:real;

clrscr;

n:=0; x0:=-2; x:=x0; y0:=-4; y:=y0; eps:=0.001;

writeln (" n x(i) x(i+1) x(i+1)-x(i) y(i) y(i+1) y(i+1)-y(i) ");

xn:=x-(1/(x+y))*(x*x-x*y+2*x+x-y+2);

yn:=y-(1/(x+y))*(x*y*(-y)-3*(-y)+x*y-3);

writeln (n:3, x:9:5, xn:9:5, abs(xn-x):9:5, y:9:5, yn:9:5, abs(yn-y):9:5);

n:=n+1;

until (abs(x-zx)<=eps) and (abs(y-zy)<=eps);

Результаты отработки программы:

· Рис.2 – программы, работающей по методу простых итераций;

· Рис.3 – программы, работающей по методу Ньютона.

Рис.2 Ответ: х(16)≈-3.00023, у(16)≈-1.00001

Рис.3 Ответ: х(8)≈-3.00000, у(8)≈-1.00000

Решение нелинейных уравнений

Пусть требуется решить уравнение

Где
– нелинейная непрерывная функция.

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

Полное решение поставленной задачи можно разделить на 3 этапа:

Установить количество, характер и расположение корней уравнения (1).

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

Найти значение корней с требуемой точностью (уточнить корни).

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

Наиболее наглядный метод отделения корней уравнения (1) состоит в определении координат точек пересечения графика функции
с осью абсцисс. Абсциссы точек пересечения графика
с осью
являются корнями уравнения (1)

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

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

Если функция
удовлетворяет условиям теоремы Больцано-Коши и монотонна на этом отрезке, то на
существует только один корень уравнения (1).Таким образом, уравнение (1) имеет на
единственный корень, если выполняются условия:

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

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

Решение третьей задачи осуществляется различными итерационными (численными) методами: методом дихотомии, методом простой итерации, методом Ньютона, методом хорд и т.д.

Пример Решим уравнение
методом простой итерации . Зададим
. Построим график функции.

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

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

(3)

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

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

На практике часто выражают
непосредственно из уравнения (1). Если не выполняется условие сходимости, преобразуют его к виду (3) и подбирают. Представим наше уравнение в виде
(выразим x из уравнения). Проверим условие сходимости метода:

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

Выберем
. Организуем итерации по формуле:

Программно организуем процесс итераций с заданной точностью:

> fv:=proc(f1,x0,eps)

> k:=0:

x:=x1+1:

while abs(x1-x)> eps do

x1:=f1(x):

print(evalf(x1,8)):

print(abs(x1-x)):

:printf("Кол. итер.=%d ",k):

end :

На 19 итерации мы получили корень нашего уравнения

c абсолютной погрешностью

Решим наше уравнение методом Ньютона . Итерации в методе Ньютона осуществляются по формуле:

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

.

В нашем обозначении
и условие сходимости выполняется на отрезке
, что видно на графике:

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

Программно организуем процесс итераций с заданной точностью. На 4 итерации получим корень уравнения

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

методом Ньютона с
, находим корень уравнения на [-1,5;-1]:

Задание : Решить нелинейные уравнения с точностью

0.

деления отрезка пополам (дихотомии)

простой итерации.

Ньютона (касательных)

секущих – хорд.

Варианты заданий рассчитываются следующим образом: номер по списку делится на 5 (
), целая часть соответствует номеру уравнения, остаток – номеру метода.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СУМСКИЙ ГОСУДАСТВЕННЫЙ УНИВЕРСИТЕТ

кафедра информатики

КУРСОВАЯ РАБОТА

ПО КУРСУ:

Численные методы

«Итерационные методы решения систем нелинейных уравнений»

1. Методы решения систем нелинейных уравнений. Общая информация

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

2.2 Преобразование Эйткена

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

2.3.1 Модификации метода Ньютона

2.3.2 Квазиньютоновские методы

2.4 Другие итерационные методы решения систем нелинейных уравнений

2.4.1 Метод Пикара

2.4.2 Метод градиентного спуска

2.4.3 Метод релаксаций

3. Реализация итерационных методов программно и с помощью математического пакета Maple

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

3.2 Метод градиентного спуска

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

3.4 Модифицированный метод Ньютона

Список использованной литературы

1. Методы решения нелинейных уравнений. Общая информация.

Пусть нам дана система уравнений, где

- некоторые нелинейные операторы: (1.1)

Она может быть также представлена в матричном виде:

(1.1)

Её решением называется такое значение

, для котрого

Очень распространенной является вычислительная задача нахождения некоторых или всех решений системы (1.1) из n нелинейных алгебраических или трансцендентных уравнений с n неизвестными.

Обозначим через Х вектор-столбец (х 1 , х 2 ,..., х n ) T и запишем систему уравнений в виде формулы (1.2): F (Х ) = 0, где F = (f 1 , f 2 ,..., f n ) T .

Подобные системы уравнений могут возникать непосредственно, например, при конструировании физических систем, или опосредованно. Так, к примеру, при решении задачи минимизации некоторой функции G (х )часто необходимо определить те точки, в которых градиент этой функции равен нулю. Полагая F = grad G, получаем нелинейную систему.

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

. Если итерационный процесс сходится, то граничное значение является решением данной системы уравнений.

Для полноты представления о методах нахождения решения системы необходимо разъяснить такое понятие, как "скорость сходимости". Если для последовательности x n , сходящейся к пределу х * , верна формула

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

2. Итерационные методы решения систем нелинейных уравнений

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

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

f i (x 1 ,x 2 ,...x n) = 0, i =1,2,..n ;

Приведём систему уравнений к специальному виду:

(2.1)

Или в векторном виде

. (2.2)

Причем переход к этой системе должен быть только при условии, что

является сжимающим отображением.

Используя некоторое начальное приближение X (0) = (x 1 (0) ,x 2 (0) ,...x n (0))

построим итерационный процесс X (k+1) =  (X (k)). Расчёты продолжаются до выполнения условия

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

Проведём обоснование метода в некоторой норме

пространства .

Приведём теорему о сходимости, выполнение условий которой приводит к нахождению решения системы.

Теорема (о сходимости). Пусть

1). Вектор-функция Ф(х) определена в области

; выполняется условие

3). Справедливо неравенство

Тогда в итерационном процессе:

, – решение системы уравнений; ,

Замечание. Неравенство условия 2) есть условие Липшица для вектор -функции Ф(х) в области S с константой

(условие сжатия). Оно показывает, что Ф является оператором сжатия в области S , т. е. для уравнения (2.2) действует принцип сжатых отображений. Утверждения теоремы означают, что уравнение (2.2) имеет решение в области S , и последовательные приближения сходятся к этому решению со скоростью геометрической последовательности со знаменателем q .

Доказательство . Поскольку

, то для приближения в силу предположения 3) имеем . Это значит, что . Покажем, что , k=2,3,… причём для соседних приближений выполняется неравенство (2.3)

Будем рассуждать по индукции. При

утверждение справедливо, т.к. и . Допустим, что приближения принадлежат S, и неравенство (2.3) выполнено для . Поскольку , то для с учётом условия 2) теоремы имеем .

По индуктивному предположению