Нелинейных уравнений методом ньютона курсовая работа

Курсовая работа: Метод Ньютона для решения нелинейных уравнений

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«Приднестровский государственный университет им. Т.Г. Шевченко»

Кафедра физики, математики и информатики

по дисциплине: «Практикум по решению задач на ЭВМ»

«Метод Ньютона для решения нелинейных уравнений»

студентка III курса;

с доп. специальностью английский

преподаватель Панченко Т. А.

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

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

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

Цели и задачи.

Целью данной курсовой работы является изучение и реализация в программном продукте решения нелинейных уравнений при помощи метода Ньютона. Данная работа состоит из трёх разделов, заключения и приложения. Первый раздел — теоретический и содержит общие сведения о методе Ньютона. Второй – это практическая часть. Здесь описывается метод Ньютона разобранный на конкретных примерах. Третий посвящён тестированию программы и анализу получившихся результатов. В заключении представлен вывод о проделанной работе.

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

Для этого необходимо выполнить следующие задачи:

1. Изучить необходимую литературу.

2. Обзорно рассмотреть существующие методы по решению нелинейных уравнений.

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

4. Рассмотреть решение нелинейных уравнений методом Ньютона на конкретных примерах.

5. Разработать программу для решения нелинейных уравнений методом Ньютона.

6. Проанализировать получившиеся результаты.

Рассмотрим задачу нахождения корней нелинейного уравнения

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

Алгоритм нахождения корней приближенными методами можно разбить на два этапа. На первом изучается расположение корней и проводится их разделение. Находится область [a,b], в которой существует корень уравнения или начальное приближение к корню x₀ . Простейший способ решения этой задачи является исследование графика функции f(x) . В общем же случае для её решения необходимо привлекать все средства математического анализа.

Существование на найденном отрезке [a,b], по крайней мере, одного корня уравнения (1) следует из условия Больцано:

f(a)*f(b) 0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 — о квадратичной, m=3 — о кубической сходимостях.

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

; (5,6)

или малости невязки:

(7)

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

1.1 Обзор существующих методов решения нелинейных уравнений

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

1)Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x₀ и точность ε. Первое приближение решения x₁ находим из выражения x₁ =f(x₀ ), второе — x₂ =f(x₁ ) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>ε. Условие сходимости метода итераций |f'(x)| ε. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой x_i+1 =x_i -F(x_i )\ F’(x_i ). Условие сходимости метода касательных F(x₀ )∙F»(x)>0, и др.

3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле С_к =а_к +в_к /2.

Для того чтобы выбрать из двух получившихся отрезков необходимый, надо находить значение функции на концах получившихся отрезков и рассматривать тот на котором функция будет менять свой знак, то есть должно выполняться условие f (а_к )* f (в_к ) 0 ;

x* О [a,c] , если f(c)Ч f(b) 0 ;

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

Преобразуем уравнение (1) к эквивалентному уравнению вида:

В случае метода касательных . Если известно начальное приближение к корню x=x₀ , то следующее приближение найдем из уравнения x₁ =g(x₀ ), далее x₂ =g(x₁ ). Продолжая этот процесс, получим рекуррентную формулу метода простой итерации

Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7).

Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода.

Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие , то процесс сходится, иначе – расходится (рис3(б)).

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

(12)

Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x . Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1 (0) так, чтобы выполнилось условие

Задать малое положительное число ε , как точность вычислений. Положить к = 0.

2. Вычислить х (к+1) по формуле (9) :

.

3. Если | x (k+1) — x (k) | (k+1) . Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.

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

Решить уравнение методом Ньютона.

sin x 2 + cosx 2 — 10x. = 0.

Вычисления производить с точностью ε = 0, 001.

Вычислим первую производную функции.

F’(x)=2x cosx 2 — 2x sinx 2 — 10.

Теперь вычислим вторую производную от функции.

F’’(x)=2cosx 2 — 4x 2 sinx 2 — 2sinx 2 — 4x 2 cosx 2 = cosx 2 (2-4x 2 ) — sinx 2 (2+4x 2 ).

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0) ) * f’’(x (0) ) > 0.

Пусть x (0) = 0, 565, тогда f(0. 565)*f’’(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0,

Условие выполняется, значит берём x (0) = 0, 565.

Теперь составим таблицу значений, для решения данного уравнения.

Отсюда следует, что корень уравнения х = 0, 101.

Решить уравнение методом Ньютона.

cos x – e -x2/2 + x — 1 = 0

Вычисления производить с точностью ε = 0, 001.

Вычислим первую производную функции.

F’(x) = 1 – sin x + x*e -x2/2 .

Теперь вычислим вторую производную от функции.

F’’(x) = e -x2/2 *(1-x 2 ) – cos x.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0) ) * f’’(x (0) ) > 0.

Пусть x (0) = 2, тогда f(2)*f’’(2) = 0. 449 * 0. 010 = 0.05 > 0,

Условие выполняется, значит берём x (0) = 2.

Теперь составим таблицу значений, для решения данного уравнения.

Отсюда следует, что корень уравнения х = 1. 089.

Решить уравнение методом Ньютона.

Вычисления производить с точностью ε = 0, 001.

Вычислим первую производную функции.

Теперь вычислим вторую производную от функции.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0) ) * f’’(x (0) ) > 0.

Пусть x (0) = 1, тогда f(2)*f’’(2) = 0. 632 * 1, 632 = 1, 031 > 0,

Условие выполняется, значит берём x (0) = 1.

Теперь составим таблицу значений, для решения данного уравнения.

Отсюда следует, что корень уравнения х = 0, 703.

Решить уравнение методом Ньютона.

Вычислим первую производную функции.

F’(x) = -sin x + e -x/2 /2+1.

Теперь вычислим вторую производную от функции.

F’’(x) = -cos x — e -x/2 /4.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0) ) * f’’(x (0) ) > 0.

Пусть x (0) = 1, тогда f(2)*f’’(2) = -0. 066 * (-0. 692) = 0. 046 > 0,

Условие выполняется, значит берём x (0) = 1.

Теперь составим таблицу значений, для решения данного уравнения.

Отсюда следует, что корень уравнения х = 1. 162.

Решить уравнение методом Ньютона.

Вычислим первую производную функции.

Теперь вычислим вторую производную от функции.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0) ) * f’’(x (0) ) > 0.

Пусть x (0) = 1, тогда f(2)*f’’(2) = 0. 350 * 2, 350 = 0. 823 > 0,

Условие выполняется, значит берём x (0) = 1.

Теперь составим таблицу значений, для решения данного уравнения.

Отсюда следует, что корень уравнения х = 0, 881.

3.1 Описание программы

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

1. модуль Crt предназначен для обеспечения контроля над текстовыми режимами экрана, расширенными кодами клавиатуры, цветами, окнами и звуком;

2. модуль Graph предназначен для обеспечения контроля над графическими объектами;

3. procedure GrafInit — инициализирует графический режим;

4. function VF – вычисляет значение функции;

5. function f1 – вычисляет значение первой производной функции;

6. function X_Newt – реализует алгоритм решения уравнения методом Ньютона.

7. procedure FGraf – реализует построение графика заданной функции f(x);

Ots=35 — константа, определяющая количество точек для отступа от границ монитора;

fmin, fmax – максимальные и минимальные значения функции;

SetColor(4) – процедура, которая устанавливает текущий цвет графического объекта, используя палитру, в данном случае это красный цвет;

SetBkColor(9) – процедура, которая устанавливает текущий цвет фона, используя палитру, в данном случае – это светло-синий цвет.

8. Procedure MaxMinF – вычислят максимальные и минимальные значения функции f(x).

Line – процедура, которая рисует линию из точки с координатами (x1, у1) в точку с координатами (х2, у2);

MoveTo – процедура, перемещающая указатель (СР) в точку с координатами (х, у);

TextColor(5) – процедура, устанавливающая текущий цвет символов, в данном случае – это розовый;

Outtexty(х, у, ‘строка’) – процедура, которая выводит строку, начиная с позиции (х, у)

CloseGraph – процедура, закрывающая графическую систему.

3.2 Тестирование программы

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

1) sin x 2 + cosx 2 — 10x. = 0.

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

Введите точность вычисления eps=0. 01

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0000002

2) cos x – e -x2/2 + x — 1 = 0.

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

Введите точность вычисления eps=0. 001

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=-0, 0000000

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

Введите точность вычисления eps=0. 01

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0000000

4) cos x –e -x/2 +x-1=0.

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

Введите точность вычисления eps=0. 001

Корень уравнения, найденный методом Ньютона:

сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0008180

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

Введите точность вычисления eps=0. 001

Корень уравнения, найденный методом Ньютона:

Сделаем проверку, подставив полученный ответ в уравнение.

Получим : х=0, 0000000

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

1.Изучена необходимая литература.

2.Обзорно рассмотрены существующие методы по решению нелинейных уравнений.

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

4.Рассмотрено решение нелинейных уравнений методом Ньютона на примере.

5.Проведены тестирование и отладка программы.

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

1. Б.П. Демидович, И.А Марон. Основы вычислительной математики. – Москва, изд. «Наука»; 1970.

2. В.М. Вержбицкий. Численные методы (линейная алгебра и нелинейные уравнения). – Москва, «Высшая школа»; 2000.

3. Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков. Численные методы в задачах и упражнениях. – Москва, «Высшая школа»; 2000.

4. Мэтьюз, Джон, Г.,Финк, Куртис, Д. Численные методы MATLAB, 3-е издание.- Москва, «Вильяс»; 2001.

Нелинейных уравнений методом ньютона курсовая работа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Метод спуска

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

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

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

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

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

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

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

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

) f ¢ (x) ¹ 0 при 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 сначала удобно выбирать один из концов отрезка.

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

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

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

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

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

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

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

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

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

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e — до выполнения неравенства | xi-xi-1| ¢ (x) и f ² (x), причем f ¢ (x) ¹ 0 при x Î [a;b], f ¢ (x) и f ² (x) должны сохранять знак на отрезке [a;b]

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

— вычисляем , пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e — до выполнения неравенства | xi-xi-1| 1,30,253137-1,470291,5-0,26435-0,12004

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.1 Метод итераций

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

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

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

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

где ? — заданная точность решения;

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

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

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

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

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

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

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

Из графика видим, что система имеет одно решение, заключенное в области D: 0 00,15-2-0,45-0,435-0,4161-0,138710,16128-2,035-0,4387-0,4248-0,4477-0,149220,15077-2,0248-0,4492-0,4343-0,4385-0,146230,15382-2,0343-0,4462-0,4315-0,4471-0,14940,15098-2,0315-0,449-0,4341-0,4446-0,148250,1518-2,0341-0,4482-0,4333-0,4469-0,14960,15104-2,0333-0,449-0,434-0,4462-0,148770,15126-2,034-0,4487-0,4338-0,4468-0,148980,15105-2,0338-0,4489-0,434-0,4467-0,1489

Так как . где , то

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

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

Пусть известно приближение xi(k) решения системы нелинейных уравнений xi*. Введем в рассмотрение поправку Dxi как разницу между решением и его приближением:

Подставим полученное выражение для xi* в исходную систему.

Неизвестными в этой системе нелинейных уравнений являются поправки Dxi. Для определения Dxi нужно решить эту систему. Но решить эту задачу так же сложно, как и исходную. Однако эту систему можно линеаризовать, и, решив ее, получить приближенные значения поправок Dxi для данного приближения, т.е. Dxi(k). Эти поправки не позволяют сразу получить точное решение , но дают возможность приблизиться к решению, — получить новое приближение решения

Для линеаризации системы следует разложить функцию f i в ряды Тейлора в окрестности x i (k) , ограничиваясь первыми дифференциалами.

Полученная система имеет вид:

Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения x i (k) . Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n — метод исключения Гаусса.

Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности e , расчет завершается. Таким образом, условие окончания расчета:

Можно использовать и среднее значение модулей поправок:

В матричной форме систему можно записать как:

где: , — матрица Якоби (производных),

W(X(k)) — матрица Якоби, вычисленная для очередного приближения.

F(X(k)) — вектор-функция, вычисленная для очередного приближения.

Выразим вектор поправок ?X(k) из :

где W-1 — матрица, обратная матрице Якоби.

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

Достаточные условия сходимости для общего случая имеют очень сложный вид, и на практике проверяются редко. Нужно отметить, что метод сходится очень быстро (за 3 — 5 итераций), если det|W| ¹ 0 и начальное приближение X (0) выбрано близким к решению (отличаются не более чем на 10%).

Алгоритм решения СНУ методом Ньютона состоит в следующем:

1) Задается размерность системы n, требуемая точность ?, начальное приближенное решение .

) Вычисляются элементы матрицы Якоби

) Вычисляется обратная матрица .

) Вычисляется вектор функция , , .

) Вычисляются вектор поправок

) Оценивается достигнутая точность

) Проверяется условие завершения итерационного процесса .

Если оно не соблюдается, алгоритм выполняется снова с пункта 2.

Для уменьшения количества арифметических действий Рафсон предложил не вычислять обратную матрицу W-1, а вычислять поправки как решение СЛУ: , данный метод получил название метод Ньютона-Рафсона.

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

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

Используя метод Ньютона, решить систему нелинейных уравнений с точностью до 0,002.

Отделение корней производим графически.

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

Значения для x можно брать исходя из следующих условий:

из первого уравнения -1 -0.76

За начальное приближение примем x 0 =0.4; y 0 =-0.75.

Имеем следующие системы:

Найдем элементы матрицы Якоби , где , и значения функций в x0=0.4; y0=-0.75:

Все вычисления производим в таблице.

nxn0.8xn22xn-ynsin(2xn-yn)F(xn,yn) detWdetW1?xyn1.5yn2cos(2xn-yn)G(xn,yn) detW2?y00,4000,12801,550,999780,11978-1,15841-0,020792,61970,27010,1031-0,7500,843750,02079-0,028250,64000-2,250000,043940,0167710,50310,202491,739430,98581-0,01791-1,535680,167843,2429-0,0379-0,0117-0,73320,80644-0,16780,008930,80496-2,19969-0,0007-0,000220,49140,193191,716280,98944-0,00026-1,489940,144973,164-0,0006-0,0002-0,73340,80692-0,14490,000110,78627-2,20034-0,00005-0,00001

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

Курсовая работа по дисциплине «Численные методы» на тему: «Метод Ньютона и его модификации решения систем нелинейных уравнений» (стр. 1 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4

Федеральное агентство по образованию

Сочинский государственный университет туризма и курортного дела

Кафедра общей математики

Курсовая работа по дисциплине

«Метод Ньютона и его модификации решения систем нелинейных уравнений»

студентка 3 курса

1. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. 3

ВЕКТОРНАЯ ЗАПИСЬ НЕЛИНЕЙНЫХ СИСТЕМ. 3

1.2. ОСНОВНАЯ ТЕОРЕМА О СХОДИМОСТИ МЕТОДА НЬЮТОНА. 3

1.3. КРИТЕРИЙ ОКОНЧАНИЯ. 3

2. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. 3

2.1. ОПИСАНИЕ МЕТОДА. 3

2.2. СХОДИМОСТЬ МЕТОДА. 3

2.3. ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ. 3

3. МОДЕФИКАЦИЯ МЕТОДА НЬЮТОНА. 3

3.1. УПРОЩЁННЫЙ МЕТОД НЬЮТОНА. 3

3.2. ИСПОЛЬЗОВАНИЕ ФОРМУЛ ЧИСЛЕННОГО ДИФФЕРЕНЦИРОВАНИЯ. 3

3.3. МЕТОД ЛОЖНОГО ПОЛОЖЕНИЯ. 3

3.4. МЕТОД СЕКУЩИХ. 3

3.5. МЕТОД СТЕФФЕНСЕНА. 3

4. ЧИСЛЕННЫЙ ПРИМЕР. 3

5. ЛИСТИНГ ПРОГРАММЫ НА ЯЗЫКЕ MATHCAD.. 3

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ. 3

ВВЕДЕНИЕ.

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

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

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

1. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

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

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

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

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

. (1.1)

Полагая в равенстве (1.1) , замечаем, что при выполнении условия абсцисса точки пересечения касательной с осью удовлетворяет равенству:

. (1.2)

Выражая из него , получаем расчётную формулу метода Ньютона:

, . (1.3)

Благодаря такой геометрической интерпретации этот метод часто называют методом касательных.

ВЕКТОРНАЯ ЗАПИСЬ НЕЛИНЕЙНЫХ СИСТЕМ.

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

(1)

где— заданные, нелинейные (среди них могут быть и линейные)

вещественнозначные функции п вещественных переменных . Обозначив

, ,

данную систему (2.1) можно записать одним уравнением

(2)

относительно векторной функции F векторного аргумента х. Таким образом, исходную задачу можно рассматривать как зада­чу о нулях нелинейного отображения В этой постановке она является прямым обобщением основной задачи предыдущей главы — задачи построения методов нахождения нулей одномерных нелинейных отображений. Фактически это та же задача, только в пространствах большей размерности. Поэтому можно как заново строить методы ее решения на основе разработанных выше подходов, так и осуществлять формальный перенос выведенных для скалярного случая расчетных формул. В любом случае следует позаботиться о правомочности тех или иных операций над векторными переменными и векторными функциями, а также о сходимости получаемых таким способом итерационных процессов. Часто теоремы сходимости для этих процессов являются тривиальными обобщениями соответствующих результатов, полученных для методов решения скалярных уравнений. Однако не все результаты и не все методы можно перенести со случая п = 1 на случай п ≥2. Например, здесь уже не будут работать методы дихотомии, поскольку множество векторов не упорядочено. В то же время, переход от n = 1 до n≥2 вносит в задачу нахождения нулей нелинейного отображения свою специфику, учет которой приводит к новым методам и к различным модификациям уже имеющихся. В частности, большая вариативность методов решения нелинейных систем связана с разнообразием способов, которыми можно решать линейные алгебраические задачи, возникающие при пошаговой линеаризации данной нелинейной вектор-функции F(x).

2) Метод линеаризации.

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

Пусть приближение уже получено. Представим функцию в окрестности точки по формуле Тейлора:

. (1.4)

Здесь — некоторая точка, расположенная между и . Заменяя в уравнении функцию главной линейной частью разложений (1.4), получим линейное уравнение:

. (1.5)

Принимая решение уравнения (5) за новое приближение , приходим к формуле (1.3).

1.2. ОСНОВНАЯ ТЕОРЕМА О СХОДИМОСТИ МЕТОДА НЬЮТОНА.

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