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

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

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

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

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

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

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

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

Одобрено

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

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

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

Саратов 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ⁿ можно рассматривать как функцию многих переменных .

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

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

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

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

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

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

.

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

.

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

или .

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

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

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

т. е. .

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

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

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

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

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

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

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

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

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

Сходимость процесса простой итерации зависит от двух условий. Первое условие состоит в том, что какая-нибудь точка должна оказаться близкой к исходному решению. Степень необходимой близости зависит от функций _{1, 2},. .. , _n. Это требование не относится к системам линейных уравнений, для которых сходимость процесса простой итерации зависит только от второго условия.

Второе условие связано с матрицей, составленной из частных производных первого порядка функций _{1, 2},. .. , _n — матрицей Якоби

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

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

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

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

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

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

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

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

где L — постоянная 0 L 1,

4) Числа b, N, r подчинены условию 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, начальное приближение выбрать произвольно или графически, (0,1).

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