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

Способы отделения корней. Решение задачи методами Ньютона уточнения корней и простых итераций. Формула нахождения погрешностей. Геометрическая интерпретация методов. Составление блок-схем и текстов программ. Результаты их работы на тестовом примере.
Краткое сожержание материала:

Размещено на

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

ФГОУ СПО «Уфимский авиационный техникум»

Курсовая работа

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

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

Введение

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

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

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

Задание при обработке на ЭВМ проходит ряд шагов: компиляцию, редактирование (компоновку) и выполнение.

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

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

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

1. Теоретическая часть

Рассмотрим уравнение вида

, (1)

где -- любая нелинейная или трансцендентная функция, например

.

Для нахождения корней уравнения (1) различают следующие два этапа.

1. Отделение корней, т.е. нахождение таких интервалов по аргументу x, внутри каждого из которых существует только один корень уравнения (1).

2. Уточнение корней заключается в применении некоторого итерационного метода, в результате которого корень уравнения (1) может быть получен с любой наперед заданной точностью ?. При этом, останавливая процесс на какой-либо конечной итерации, необходимо оценить погрешность по сравнению с точным корнем, который неизвестен.

Способы отделения корней.

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

1. Графический.

2. Метод половинного деления.

В графическом способе строится график функции (рисунок 1) и приближенно определяются ее нули (или корни уравнения) Заключив эти нули в интервалы



Рисунок 1. Графический метод отделения корней

, на границах которых выполняются условия, i=1, 2, …, и знаки производных первого и второго порядков , на интервалах постоянны, можно утверждать, что внутри каждого из этих интервалов находится один корень уравнения (1)

Если при этом , a , то корень --

двукратный корень (точка на рисунке 1); если ,

a , то -- трехкратный корень (точка на рисунке 1) и т. д.

В методе половинного деления область определения функции делят на 2, 4, 8, 16, 32, ... интервала и для каждого из них анализируют знаки функции на концах интервала; если они противоположны, то внутри интервала находится не менее одного корня; если знак первой производной на интервале постоянный, т.е. (при выполнении предыдущего условия), то внутри интервала находится точно один корень. В данном параграфе рассматриваются однократные (простые) вещественные корни нелинейных уравнений (1).

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

Для этого построим невязку, т. к.. Применим к невязке теорему Лагранжа о конечных приращениях:

Откуда

.

Так как точное значение ? неизвестно, эту погрешность заменяют верхней оценкой:

. (2)

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

1.1 Метод Ньютона уточнения корней

Пусть для уравнения (1) на интервале отделен корень. В методе Ньютона функция должна удовлетворять на отрезке следующим условиям:

1) существование производных 1-го и 2-го порядков;

2) ;

3)производные 1-го и 2-го порядков знакопостоянны на отрезке.

Пусть имеется значение корня на k-й итерации -- . Тогда значение корня на (k+1)-й итерации вычисляется следующим образом:

, (3)

где -- шаг, который подлежит определению.

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

,

.

Положим в этом разложении линейную относительно часть равной нулю, в результате чего находим значение шага :

,

подставляя которое в (3) , получаем

(4)

За начальное приближение принимается один из концов отрезка [a,b], а именно

(5)

Выражения (4), (5) называют итерационным методом Ньютона (или касательных) уточнения корней нелинейного уравнения (1).

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

, k = 0, 1, 2… (6)

Метод (5), (6) называют модифицированным методом Ньютона. Он обладает неоспоримым преимуществом перед методом (4), (5), но сходится медленнее.

Справедлива следующая теорема.

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

, (7)

, ,

Действительно, поскольку f(x) непрерывна, то взяв предел от (4) при и поменяв местами знаки предела и функции, получим

.

Поскольку последовательность -- невозрастающая (неубывающая) числовая последовательность, ограниченная снизу (сверху), то она сходится, т.е. существует предел . Тогда из последнего равенства ( по условию) имеем

, откуда ,

т.е. предельное значение является корнем уравнения (1).

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

,

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

Рисунок 2. Метод Ньютона

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

Поскольку верхняя оценка (7) сложна для вычисления, на практике итерационный процесс останавливают при выполненииn условия , , где - заданная точность.

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

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

Метод простых итераций уточнения корней уравнения (1) состоит в замене этого уравнения эквивалентным ему уравнением

(8)

и построении последовательности

(9)

где , например .

Если не удается выразить х из уравнен...