Метод ньютона для нелинейного уравнения паскаль
Pers.narod.ru. Алгоритмы. Метод Ньютона решения нелинейного уравнения
В литературе называется также методом касательных.
Рассмотрим графическую иллюстрацию метода (рис. 1). Предположим, что графическим методом определено начальное приближение х0 к корню. В точке х0 вычислим левую часть решаемого уравнения f0 = f(x0), а также производную в этой точке f'(x0) = tg α. Следующее приближение к корню найдем в точке х1, где касательная к функции f(x), проведенная из точки (х0, f0), пересекает ось абсцисс. Затем считаем точку х1 в качестве начальной и продолжаем итерационный процесс. Из рис. видно, что таким способом можно приближаться к корню х*. При этом с каждой итерацией расстояние между очередным хk+1 и предыдущим хk приближениями к корню будет уменьшаться. Процесс уточнения корня закончим, когда выполнится условие
Метод Ньютона обладает высокой скоростью сходимости. Обычно абсолютная точность решения 10 -5 — 10 -6 достигается через 5-6 итераций.
Недостатком метода является необходимость вычисления на каждой итерации не только левой части уравнения, но и её производной.
Можно, несколько уменьшив скорость сходимости, ограничиться вычислением производной f'(x) только на первой итерации, а затем вычислять лишь значения f(x), не изменяя производной f'(x). Это алгоритм так называемого модифицированного метода Ньютона (рис. 2).
Ниже приводится простая консольная программа на Паскале для решения алгебраического уравнения произвольной степени n>1 . Функция f(x) и первая производная f'(x) задаются подпрограммами-функциями f и f1 соответственно.
Решение нелинейных уравнений на языке программирования Pascal
Практически перед каждым программистом рано или поздно встает задача определения корней уравнения. На сегодняшний день существует достаточно много алгоритмов решения данной задачи. Из этой статьи вы узнаете о наиболее известных алгоритмах численного решения уравнений. Практически все они могут быть разделены на два этапа: отделения и уточнения корней. Первую часть легко выполнить графическим методом. Для выполнения второго этапа решения уравнения можно воспользоваться одним из многих методов уточнения корней уравнения.
Наиболее простым в реализации является метод бисекции, или как его еще называют, метод половинного деления. Это итерационный метод, суть которого заключается в том, что на каждой итерации интервал сокращается вдвое до тех пор, пока не будет найдено решение с заданной точностью.
Данный метод достаточно прост и содержит всего два действия. Сначала находится переменная х – середина интервала [a,b]. После чего вычисляется значение функции в середине интервала. Затем определяется, совпадает ли по знаку значение функции в середине интервала, со знаком функции в левой части. В случаи если их знаки равны, то новой левой границей считается середина интервала, в ином же случаи правой граница интервала считается его середина. Таким образом, при каждой итерации интервал сокращается вдовое то справа, то слева. Очень часто можно встретить следующую реализацию данного метода.
Этот вариант, хотя и очень прост для понимания, содержит один недостаток. Дело в том, что если функция очень сильно изменяется, то при заданной точности, её значение может очень сильно отличаться. Поэтому для исключения этой неточности выгоднее использовать цикл с постусловием и сравнивать с заданным значением точности не разницу границ интервала, а значение функции. Тогда реализация метода примет следующий вид.
Другим очень хорошим методом нахождения корней уравнения, который несколько сложнее в реализации, чем предыдущий, является метод хорд. Отличается он тем, что границы интервала соединяются прямой линией, то есть хордой. Затем определяется точка пересечения этой прямой с осью абсцисс, по формуле:
После чего находится значение функции в точке пересечения. По аналогии с предыдущим методом определяется новая левая или правая граница интервала, которой является точка пересечения. Реализация данного метода на языке программирования Pascal может быть представлена следующим образом.
Еще одним хорошим методом решения уравнений является метод касательных или метод Ньютона. Главное его отличие от представленных ранее методов биссекции и хорд – отсутствие необходимости отделения корня. Вместо этого нужно задать лишь начальное приближение. Однако его главным недостатком остается сложность реализации, связанная, прежде всего с необходимостью определять производные исходного уравнения.
В основе метода Ньютона лежит разложения функции в ряд Тейлора:
Обычно значения ряда, содержащие шаг h во второй и более высоких степенях отбрасывают, так как их влияние на результат незначительны.
Суть метода заключается в экстраполяции функции касательными. После того как пользователь задает начальное приближение, программа должна определить точку пересечения касательной к графику функции с осью абсцисс. Для этого используется формула:
Затем находится значение функции в точке пересечения касательной с осью абсцисс и если получившиеся значение близко к нулю, то считается, что решение уравнения найдено. Реализация данного метода может быть представлена следующим образом
К сожалению, при всех своих достоинствах метод Ньютона не гарантирует сходимости. Отсутствия решения может возникнуть по нескольким причинам. Например, это может произойти из-за того, что касательная будет параллельна оси абсцисс. В этом случаи необходимо предусмотреть выход из цикла при достижении большого количества итераций.
Существуют также и другие методы, например, золотого сечения. Какой из них использовать решать вам, однако следует отметить, что наиболее быстродейственным считается метод Ньютона, затем метод хорд и последним по быстродействию является метод половинного деления. Хотя количество итераций напрямую зависит от введенных начальных данных. При удачном стечении обстоятельств решение каждым из методов может быть найдено даже при единственной итерации.
Курсовая работа: Метод Ньютона для решения нелинейных уравнений
Название: Метод Ньютона для решения нелинейных уравнений Раздел: Рефераты по информатике Тип: курсовая работа Добавлен 01:06:49 13 декабря 2010 Похожие работы Просмотров: 3968 Комментариев: 22 Оценило: 5 человек Средний балл: 3.6 Оценка: неизвестно Скачать | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 0. 565 | -4. 387 | -9. 982 | 0. 473 |
1 | 0. 092 | 0. 088 | -9. 818 | 0. 009 |
2 | 0. 101 | 0. 000 | -9. 800 | 0. 000 |
3 | 0. 101 |
Отсюда следует, что корень уравнения х = 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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 2 | 0. 449 | 0. 361 | 1. 241 |
1 | -0. 265 | 0. 881 | 0. 881 | 0. 301 |
2 | -0. 021 | 0. 732 | 0. 732 | 0. 029 |
3 | 0. 000 | 0. 716 | 0. 716 | 0. 000 |
4 | 1. 089 |
Отсюда следует, что корень уравнения х = 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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 1, 000 | 0, 632 | 2, 368 | 0, 267 |
1 | 0, 733 | 0, 057 | 1, 946 | 0, 029 |
2 | 0, 704 | 0, 001 | 1, 903 | 0, 001 |
3 | 0, 703 |
Отсюда следует, что корень уравнения х = 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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 1, 000 | -0. 066 | 0. 462 | 0. 143 |
1 | 1. 161 | -0. 007 | 0. 372 | 0. 018 |
2 | 1. 162 | 0. 0001. | 0. 363 | 0. 001 |
3 | 1. 162 |
Отсюда следует, что корень уравнения х = 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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 1, 000 | 0, 350 | 3, 086 | 0, 114 |
1 | 0, 886 | 0, 013 | 2, 838 | 0, 005 |
2 | 0, 881 | 0, 001 | 2, 828 | 0, 000 |
3 | 0, 881 |
Отсюда следует, что корень уравнения х = 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.
http://tpdn.ru/library/articles/52/13520
http://www.bestreferat.ru/referat-258487.html