Практически перед каждым программистом рано или поздно встает задача определения корней уравнения. На сегодняшний день существует достаточно много алгоритмов решения данной задачи. Из этой статьи вы узнаете о наиболее известных алгоритмах численного решения уравнений. Практически все они могут быть разделены на два этапа: отделения и уточнения корней. Первую часть легко выполнить графическим методом. Для выполнения второго этапа решения уравнения можно воспользоваться одним из многих методов уточнения корней уравнения.
Наиболее простым в реализации является метод бисекции, или как его еще называют, метод половинного деления. Это итерационный метод, суть которого заключается в том, что на каждой итерации интервал сокращается вдвое до тех пор, пока не будет найдено решение с заданной точностью.
Данный метод достаточно прост и содержит всего два действия. Сначала находится переменная х – середина интервала [a,b]. После чего вычисляется значение функции в середине интервала. Затем определяется, совпадает ли по знаку значение функции в середине интервала, со знаком функции в левой части. В случаи если их знаки равны, то новой левой границей считается середина интервала, в ином же случаи правой граница интервала считается его середина. Таким образом, при каждой итерации интервал сокращается вдовое то справа, то слева. Очень часто можно встретить следующую реализацию данного метода.
Этот вариант, хотя и очень прост для понимания, содержит один недостаток. Дело в том, что если функция очень сильно изменяется, то при заданной точности, её значение может очень сильно отличаться. Поэтому для исключения этой неточности выгоднее использовать цикл с постусловием и сравнивать с заданным значением точности не разницу границ интервала, а значение функции. Тогда реализация метода примет следующий вид.
Другим очень хорошим методом нахождения корней уравнения, который несколько сложнее в реализации, чем предыдущий, является метод хорд. Отличается он тем, что границы интервала соединяются прямой линией, то есть хордой. Затем определяется точка пересечения этой прямой с осью абсцисс, по формуле:
После чего находится значение функции в точке пересечения. По аналогии с предыдущим методом определяется новая левая или правая граница интервала, которой является точка пересечения. Реализация данного метода на языке программирования Pascal может быть представлена следующим образом.
Еще одним хорошим методом решения уравнений является метод касательных или метод Ньютона. Главное его отличие от представленных ранее методов биссекции и хорд – отсутствие необходимости отделения корня. Вместо этого нужно задать лишь начальное приближение. Однако его главным недостатком остается сложность реализации, связанная, прежде всего с необходимостью определять производные исходного уравнения.
В основе метода Ньютона лежит разложения функции в ряд Тейлора:
Обычно значения ряда, содержащие шаг h во второй и более высоких степенях отбрасывают, так как их влияние на результат незначительны.
Суть метода заключается в экстраполяции функции касательными. После того как пользователь задает начальное приближение, программа должна определить точку пересечения касательной к графику функции с осью абсцисс. Для этого используется формула:
Затем находится значение функции в точке пересечения касательной с осью абсцисс и если получившиеся значение близко к нулю, то считается, что решение уравнения найдено. Реализация данного метода может быть представлена следующим образом
К сожалению, при всех своих достоинствах метод Ньютона не гарантирует сходимости. Отсутствия решения может возникнуть по нескольким причинам. Например, это может произойти из-за того, что касательная будет параллельна оси абсцисс. В этом случаи необходимо предусмотреть выход из цикла при достижении большого количества итераций.
Существуют также и другие методы, например, золотого сечения. Какой из них использовать решать вам, однако следует отметить, что наиболее быстродейственным считается метод Ньютона, затем метод хорд и последним по быстродействию является метод половинного деления. Хотя количество итераций напрямую зависит от введенных начальных данных. При удачном стечении обстоятельств решение каждым из методов может быть найдено даже при единственной итерации.
Видео:Метод простых итераций пример решения нелинейных уравненийСкачать
Лабораторная работа: Итерационные методы решения нелинейных уравнений
| Название: Итерационные методы решения нелинейных уравнений Раздел: Рефераты по информатике, программированию Тип: лабораторная работа Добавлен 09:43:21 25 июня 2008 Похожие работы Просмотров: 2747 Комментариев: 21 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно Скачать | |
и 
. Сделать вывод о скорости сходимости всех трех методов.
и снова решить задачу. Сделать вывод о точности полученных результатов.
(1)
.
на Рис.1 видно, что функция 
в одной точке, являющейся приближенным значением корня нелинейного уравнения (1). Но так как данная функция имеет сложный аналитический вид, то преобразуем уравнение (1) к виду 
и построим два графика 
и 
, имеющих более простой аналитический вид (Рис.2). Абсцисса точки пересечения графиков является приближенным значением корня. Заметим, что графический метод показывает количество корней исходного уравнения, но не доказывает единственность корня на отрезке. |
Рис.1
Аналитический метод. Функция 
непрерывна на отрезке 
, имеет на концах отрезка разные знаки (
), а производная функции не меняет знак на отрезке (
). Следовательно, нелинейное уравнение (1) имеет на указанном отрезке единственный корень.
2. Метод простых итераций. Для построения рабочей формулы перепишем уравнение (1) в виде: 
. Проверим, выполняется ли достаточное условие сходимости на отрезке:
(2)
Если условие выполняется, то итерационный процесс строится по формуле
Заметим, что в точке 
из отрезка , значение 
.
Построим функцию 
. Константа 
выбирается из условия (2). Если производная 
, то значение выбирается из интервала 
, если производная 
, то – из интервала 
. Так как 
всюду положительна на отрезке, то, конкретизируя значение производной в любой точке отрезка (например ), значение 
определяется из интервала 
. Выбрав значение 
, запишем рабочую формулу метода простых итераций:
(3)
Итерационный процесс (3) можно начать, задав произвольное начальное приближение 
. Процесс (3) заканчивается при одновременном выполнении двух условий: 
и 
. В этом случае значение 
является приближенным значением корня нелинейного уравнения (1) на отрезке 
.
Метод Ньютона. В качестве начального приближения 
здесь выбирается правый или левый конец отрезка, в зависимости от того, в котором выполняется достаточное условие сходимости метода Ньютона вида:
(4)
Заметим, что в точке 
условие (4) не выполняется, а в точке — выполняется. Следовательно в качестве начального приближения выбирается точка 
. Рабочая формула метода Ньютона 
для данной задачи запишется так:
(5)
Условия выхода итерационного процесса (5) аналогичны условиям метода простых итераций.
Модифицированный метод Ньютона. Начальное приближение выбирается аналогично методу Ньютона, т.е. . Рабочая формула модифицированного метода Ньютона 
для данной задачи запишется так:
(6)
Условия выхода итерационного процесса (6) аналогичны условиям метода простых итераций.
Замечание: для того, чтобы сделать вывод о скорости сходимости методов, необходимо в каждом методе выбирать одинаковое начальное приближение.
3. Блок-схема метода простых итераций, метода Ньютона и модифицированного метода Ньютона приведена на рисунке 3.
 |
Ниже в качестве примера приведены программы на языках программирования Паскаль и С, реализующие итерационный процесс метода простых итераций.
ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ ПАСКАЛЬ
printf(“%d %.4f %.4f %.4f %.4fn”,n++,x,y,fabs(y-x),
Решение: в результате решения нелинейного уравнения (1) на указанном отрезке тремя методами при начальном приближении с точностью 
и 
получены следующие результаты: методом простых итераций 
; методом Ньютона 
; модифицированным методом Ньютона 
.
4. Содержание отчета.
Отчет о проделанной работе должен содержать: номер и название лабораторной работы; цель работы; содержание работы; задание на работу; теоретическую часть работы (вывод итерационных формул); листинг(и) программ(ы); таблицы результатов (в случае, если число итераций в таблице достаточно большое, в отчет занести две первых и две последних итерации); выводы о проделанной работе.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Определить количество корней исходного нелинейного уравнения графическим методом и построить график (пример приведен на рисунке 2).
2. Доказать аналитическим методом единственность корня исходного нелинейного уравнения на указанном отрезке.
3. Построить итерационные формулы, реализующие процесс поиска корня на отрезке методом простых итераций, методом Ньютона и модифицированным методом Ньютона.
4. Составить программу(ы) на любом языке программирования, реализующую(ие) построенные итерационные процессы, используя алгоритм методов, приведенный на рисунке. Печать результатов должен осуществляться на каждом шаге итераций в виде следующей таблицы:
Видео:Решение нелинейного уравнения методом простых итерацийСкачать
Решение нелинейного уравнения методом простых итераций паскаль
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 соответственно.
🎦 Видео
Алгоритмы С#. Метод простых итерацийСкачать
Метод простой итерации Пример РешенияСкачать
1 3 Решение нелинейных уравнений методом простых итерацийСкачать
Метод итерацийСкачать
2.2 Итерационные методы решения СЛАУ (Якоби, Зейделя, релаксации)Скачать
Метод Зейделя Пример РешенияСкачать
10 Численные методы решения нелинейных уравненийСкачать
4.2 Решение систем нелинейных уравнений. МетодыСкачать
Лекция №2.3 Метод простых итерацийСкачать
Метод Ньютона (метод касательных) Пример РешенияСкачать
1.1 Решение нелинейных уравнений метод деления отрезка пополам (бисекций) Мathcad15Скачать
Метод итераций (последовательных приближений)Скачать
Метод половинного деления решение нелинейного уравненияСкачать
Информатика 2. S01.E09. Лабораторная работа №3. Пример (Pascal, excel, word)Скачать
8 Метод простой итерации Ручной счет Решение системы линейных уравнений СЛАУСкачать
Численные методы, зима 2019. Задачи на метод простой итерации.Скачать
