Численные методы для решения нелинейных уравнений

Численные методы для решения нелинейных уравнений

Министерство общего и профессионального образования Российской Федерации

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

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Методические указания

к самостоятельной работе по курсу «Высшая математика»

для студентов всех специальностей

под контролем преподавателя

Одобрено

редакционно-издательским советом

Саратовского государственного

технического университета

Саратов 2008

Введение

Данная работа ориентирована на изучение некоторых численных методов приближенного решения систем нелинейных уравнений с любым числом уравнений, составление на базе этих методов вычислительных схем алгоритмов и программ на алгоритмическом языке ФОРТРАН – IV.

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

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

Предполагается, что студенты прослушали лекционный курс по основам алгоритмического языка ФОРТРАН – IV.

В качестве справочного пособия по языкам программирования может быть использована литература. [5]

Численные методы для решения нелинейных уравнений

Цель работы: изучение численных методов приближенного решения нелинейных систем уравнений, составление на базе вычислительных схем алгоритмов; программ на алгоритмическом языке ФОРТРАН – IV, приобретение практических навыков отладки и решения задач с помощью ЭВМ.

1. Определения и условные обозначения

 – конечномерное линейное пространство, элементами (точками, векторами) являются группы из  упорядоченных действительных чисел, например:

где  – действительные числа, .

В  введена операция сложения элементов, т. е.  определено отображение ,

где

Оно обладает следующими свойствами:

1.   ,

2.   ,

3.    , что  (элемент  называется нулевым),

4.   , что  (элемент  называется противоположным элементу ).

В  введена операция умножения элементов на действительные числа, т.е.  определено отображение ,

где

Оно обладает следующими свойствами:

1.   ,

2.  

Операции сложения элементов и умножения их на числа удовлетворяют законам дистрибутивности:

1.   ,

2.   .

Каждой паре элементов  поставлено в соответствие действительное число, обозначаемое символом  и называемое скалярным произведением, где

и выполнены следующие условия:

1.   ,

2.   ,

3.   ,

4.   , причем  – нулевой элемент.

Матрица  вида

 ,            (1)

где – действительные числа (,) определяет линейный оператор, отображающий линейное пространство  в себя, а именно, для

,

где .

Над линейными операторами, действующими в линейном пространстве , вводятся следующие операции:

1.   сложение операторов , при этом, если , то ,

2.   умножение операторов на числа:  при этом, если , то ,

3.   умножение операторов: , при этом, если , то .

Обратным к оператору  называется оператор  такой, что , где  – единичный оператор, реализующий тождественное отображение, а именно,

.

Пусть число  и элемент , таковы, что .

Тогда число  называется собственным числом линейного оператора , а элемент  – собственным вектором этого оператора, соответствующим собственному числу .

Линейный оператор  называется сопряженным к оператору , если для любых элементов  выполняется равенство .

Для всякого оператора  сопряженный оператор  существует, единствен; если , то .

Справедливы равенства:

1.   ,

2.   ,

3.   ,

4.   , если  существует.

Введем в рассмотрение три нормы для :

,

,

.

При этом выполняются следующие неравенства:

.

Норма элемента удовлетворяет следующим условиям (аксиомам нормы):

1.   , причем , лишь если ,

2.   ,

3.   .

Говорят, что последовательность элементов  сходится к элементу ,

а именно,            ,

или                      ,

если                     .

Определенная таким образом сходимость в конечномерном линейном пространстве  называется сходимостью по норме.

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

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

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

4.4 , причем , лишь если  – нулевая матрица,

4.4 ,

4.4 .

Введем в рассмотрение три нормы для А отображающего  в :

,

,

,

где  i-ое собственное значение матрицы .

Эти нормы линейного оператора А согласованы с соответствующими нормами элемента (вектора)  в смысле условия .

2. Основные сведения о системах нелинейных уравнений в

Общая форма систем нелинейных уравнений в  имеет вид:

         (2)

или F(x) = 0,

где  – заданные функции n переменных,  – неизвестные.

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

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

Частным случаем системы (2) является система линейных уравнений:

или ,

где А – матрица вида (1), порождающая линейный оператор, отображающий  в

Система линейных уравнений (2) поставим в соответствие линеаризованное уравнение (первые два члена из разложения в ряд Тейлора (2)) в точке  вида

   (2)

или ,

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

Для дальнейшего нам потребуется еще одна форма записи системы нелинейных уравнений в , а именно:

        (3)

или ,

где .

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

Функции  удовлетворяют тем же условиям, что и функции .

3. Отделение решений

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

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

Так, если дано скалярное уравнение , то его решение с геометрической точки зрения можно рассматривать как абсциссы точек пересечения графика функции с осью абсцисс. Построив график функции y=f (x), приближенно определяем окрестности изолированных точек пересечения графика с горизонтальной осью. Сами точки пересечения берем за начальные приближения к точным решениям.

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

Тогда нужно провести пробные решения на ЭВМ выбранным методом с исследованием сходимости.

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

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

Аналогично отделяются решения для системы двух нелинейных уравнений

   , .

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

4. Методы решения нелинейных уравнений

4.1 Метод простой итерации

Метод простой итерации (см. [1]) применяется для решения систем нелинейных уравнений с любым числом уравнений. Его можно применять как для уточнения найденного решения, так и для первоначального нахождения решения. В последнем случае, однако, метод может не дать результата.

Для применения метода простой итерации система уравнений (2) приводится к виду (3).

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

     (4)

по следующим формулам

  (5)

Замечание. Для приведения системы уравнений (2) к виду (3) можно использовать прием:

4.2 Метод Зейделя

Метод Зейделя отличается от метода простой итерации тем, что вычисления ведутся по формулам:

        (6)

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

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

Этот метод (см.[1], [4]) предложен И.Ньютоном в 1669 году, однако наиболее полное обоснование было сделано советским математиком Л.В.Канторовичем в 1949 году (см.[4]), поэтому в литературе этот метод часто называют методом Ньютона-Канторовича.

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

,

где  из уравнения (2).

Так, для к-го приближения  к точному решению  уравнения (2) ставится в соответствие линеаризованное уравнение вида (2), а именно:

или ,

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

Таким образом, последовательность (4) строится по следующим правилам:

  (),

где  – обратный оператор к линейному оператору , определяемому квадратной матрицей

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

Итерационная формула метода Ньютона при таком подходе будет иметь вид:

       (7)

 .          (8)

4.4 Модифицированный метод Ньютона

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

,         (9)

где  – начальное приближение к точному решению .

4.5 Метод Зейделя на основе линеаризованного уравнения

Итерационная формула для построения приближенного решения нелинейного уравнения (2) на основе линеаризованного уравнения (7) имеет вид:

4.6 Метод наискорейшего спуска

Методы спуска (см. [2]) сводят решение системы (2) к задаче нахождения минимума специально построенного функционала (функционал – отображение  в R), а именно:

,

где .

Функционал в конечном пространстве Rⁿ можно рассматривать как функцию многих переменных .

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

В итерационной формуле параметр h_k пока не определен, выберем его таким образом, чтобы выполнилось условие: , начиная с x⁰, в предположении, что f – монотонный функционал.

Для выбора h_k построим функционал, зависящий от параметра, который изменяется непрерывно: .

При h=0 имеем, что f (0) – линия уровня функционала, проходящая через точку x^k . Для нахождения следующей линии уровня, более близкой к минимуму, будем выбирать h таким образом, чтобы для данного x^k

Это условие минимума по h будем рассматривать как уравнение для получения h_k.

Решим его приближенно, т.к. ошибка в несколько процентов обычно не влияет на скорость сходимости. Отметим кстати, что число h_k всегда должно быть положительным. Для этого разложим функцию  в ряд Тейлора по h в точке h=0 и возьмем только линейную часть этого разложения

.

Подстановка линейной части в условие , дает уравнение для приближенного определения

.

Решая построенное уравнение относительно h, получим:

 или .

Таким образом, итерационная формула метода наискорейшего спуска имеет вид:

 или , где производные  вычислены в точке .

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

, т.е. .

5. Сходимость методов решения нелинейных уравнений

Если метод сходится, то есть , где

 – точное решение

 – k-тое приближение к точному решению, то итерационный процесс следовало бы закончить по достижению заданной погрешности , где e – заданная точность (погрешность).

Однако практически это условие выполнить нельзя, так как  неизвестно, тогда для окончания итерационного процесса можно воспользоваться неравенствами , или , где  и  – заданные величины.

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

Методы простой итерации, Зейделя, модифицированный метод Ньютона, метод наискорейшего спуска (см. [1], [2], [3], [4]) являются методами первого порядка – это значит, что имеет место неравенство , k=1, 2, . . . , где  – константа, своя у каждого метода, зависящая от выбора начального приближения , функции f_i , i = 1, 2, . . . , n, и их частных производных первого и второго порядков – точнее их оценок в некоторой окрестности искомого решения, которой принадлежит начальное приближение.

Метод Ньютона является методом второго порядка, то есть для него имеет место неравенство , k=1, 2, . . . , где  – константа, зависящая от тех же величин, что и константа .

А теперь рассмотрим достаточные условия сходимости метода простой итерации и метода Ньютона.

Сходимость процесса простой итерации зависит от двух условий. Первое условие состоит в том, что какая-нибудь точка  должна оказаться близкой к исходному решению . Степень необходимой близости зависит от функций j_1, j₂, . . . , j_n . Это требование не относится к системам линейных уравнений, для которых сходимость процесса простой итерации зависит только от второго условия.

Второе условие связано с матрицей, составленной из частных производных первого порядка функций j_1, j₂, . . . , j_n – матрицей Якоби

 ,

вычисленных в точке .

В случае, когда рассматривается система линейных алгебраических уравнений, матрица M состоит из постоянных чисел – коэффициентов, стоящих при неизвестных в правой части уравнения (3). В случае нелинейных уравнений элементы  матрицы M зависят, вообще говоря, от . Для сходимости процесса простой итерации достаточно, чтобы выполнялось неравенство:  для  из некоторой окрестности точного решения , которой должно принадлежать начальное приближение .

Приведем также достаточные условия сходимости метода Ньютона для системы уравнений вида (2) по норме .

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

1)   Матрица Якоби  системы (2) на начальном приближении имеет обратную  и известна оценка нормы обратной матрицы ,

2)   Для всех точек шара  выполнено неравенство

 при i, j = 1, 2, . . . , n ,

3)   Выполнено неравенство

,

4)   Числа b, N, r подчинены условию a = nbNr < 0,4, тогда система уравнений (2) в шаре  имеет единственное решение, к которому сходятся последовательные приближения (8) или (7’), (9’).

Для других методов условия сходимости имеют сложный вид, и мы отсылаем читателя к специальной литературе [1], [2], [3], [4].

6. Примерный перечень возможных исследований

1)   Сравнение различных методов на экономичность при решении конкретной задачи:

· по числу операций на одной итерации;

· по числу итераций, необходимых для достижения заданной точности;

2)   Зависимость числа итераций для достижения заданной точности:

· от выбора вида нормы;

· от выбора критерия окончания итерационного процесса по  или по невязке  ;

· от выбора начального приближения;

· от погрешности задания коэффициентов в уравнении.

7. Контрольные вопросы

1)   Понятие о нелинейных системах уравнений в Rⁿ.

2)   Понятие приближенного и точного решения нелинейной системы уравнений.

3)   Сущность графического метода отделения решения для системы двух нелинейных уравнений, каковы его преимущества и недостатки?

4)   Сущность метода простой итерации и метода Зейделя. Каковы условия применимости метода простой итерации?

5)   Сущность метода Ньютона и его модификации. Какова скорость сходимости метода Ньютона?

6)   Сущность метода наискорейшего спуска. Как выбирается параметр спуска?

8. Порядок выполнения курсовой работы

1)   Получить вариант задания, индивидуальный для каждого студента, у преподавателя, а именно:

Найти решение системы нелинейных уравнений в первой координатной четверти с номером – N₁ (см. варианты заданий п.10), применив для первого этапа уточнения метод с номером – N₂, а для второго этапа уточнения метод с номером – N₃ , точность вычислений на первом этапе – EPS1Î[0.1 – 0.01], на втором этапе – EPS2 Î [0.1 - 0.0001], N₄ – номер нормы, I – номер параметра a, J – номер параметра b, начальное приближение выбрать произвольно или графически, aÎ(0,1).

2)   Разработать обязательные для выполнения задания разделы данных методических указаний.