Узнать стоимость написания работы
Оставьте заявку, и в течение 5 минут на почту вам станут поступать предложения!
Реферат

Реферат по предмету "Информатика"


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

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


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

                                                            (1)

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

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

,    ,   

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

                                                                    (2)

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

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

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

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

.                          (1.4)

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

.                                               (1.5)

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



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


На практике предпочтительнее использование простой апостериорной оценки:

,                                            (1.8)

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

Теорема 2.

Пусть выполнены условия теоремы 1 и . Тогда для всех  верна оценка (8).


Из оценки (1.7) следует, что . Поэтому, применяя неравенство (6), получим цепочку неравенств:

,

из которой вытекает оценка (1.8).

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

.                                                  (1.9)

Пример 1.

Используя метод Ньютона, найдём с точностью  положительный корень уравнения .

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

.

Результаты первых итераций с 10 знаками мантиссы приведены в табл. 1.

Табл. 1







































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

Сравнение результатов итераций со значением  показывает, что приближения  содержат 1, 3, 6 верных значащих цифр соответственно. Это подтверждает отмеченный ранее факт, что при каждой итерации метода Ньютона число верных значащих цифр примерно удваивается.
Пример 2.

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

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

.                          (1.10)

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


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

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

                                               (*)

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

.

В результате придём к системе линейных алгебраических уравнений:
,

,

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .

,
имеющей в матричной форме записи вид:
.                                        (2.1)

Здесь — матрица Якоби. .

Предположим, что матрица  невырожденная, т.е. существует обратная матрица . Тогда система (2.1) имеет единственное решение, которое принимается за очередное приближение  к решению . Таким образом, приближение  удовлетворяет равенству:

,                                   (2.2)

выражая из которого , выводим итерационную формулу метода Ньютона:

.                                   (2.3)

Замечание.

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

                                             (2.4)

относительно поправки . Затем полагают:

                                                      (2.5)

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


Сформулируем основную теорему о сходимости метода Ньютона.





Теорема 3.

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

,      .
Эта оценка означает, что метод сходится с квадратичной скоростью.

Квадратичная скорость сходимости метода Ньютона позволяет использовать простой практический критерий окончания:

.                                                (2.6)

Пример 3.

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

Возьмём ,  и будем вести вычисления по формулам (2.4), (2.5), в которых

,       .

Результаты вычислений с шестью знаками мантиссы приведены в табл. 2.

Табл. 2































 

При  критерий окончания  выполняется и можно положить , .

    продолжение
--PAGE_BREAK--2.3. ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ.


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



--PAGE_BREAK--


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

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат А. С. Пушкина муниципального образования Тимашевский район «Устное народное творчество (фольклор) Кубани: традиции, обряды, песни, игры, зимние забавы…» Урок
Реферат Налоговый учет расходов на формирование резервов по сомнительным до
Реферат Соціально-економічні наслідки інфляції в Україні
Реферат Территориальное устройство Великобритании
Реферат Формирование современной профессии бухгалтера
Реферат Планирование на машиностроительном предприятии
Реферат Документы, о которых вы должны знать, когда покупаете машину
Реферат Идейно художественное своеобразие романа Дени Дидро Монахиня
Реферат Неспособность любить — свойство незрелости души
Реферат Характеристика различных способов тригонометрического нивелирован
Реферат Клиническая классификация рака легкого
Реферат «Древнегреческая мифология»
Реферат Технология производства меховых изделий
Реферат Организация труда как элемент организации на производстве
Реферат Исчисление и уплата страховых взносов во внебюджетные фонды