Министерство общего и профессионального образования Российской Федерации
Саратовский государственный технический университет
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Методические указания
к самостоятельной работе по курсу «Высшая математика»
для студентов всех специальностей
под контролем преподавателя
Одобрено
редакционно-издательским советом
Саратовского государственного
технического университета
Саратов 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
), а именно:
,
где
.
Функционал в конечном пространстве Rn
можно рассматривать как функцию многих переменных
.
Для нахождения точки
, в которой функционал f
принимает минимальное нулевое значение, выбирают точку
, находят
и строят итерационную формулу:
с начальным приближением .
В итерационной формуле параметр hk
пока не определен, выберем его таким образом, чтобы выполнилось условие:
, начиная с x
0
, в предположении, что f
– монотонный функционал.
Для выбора hk
построим функционал, зависящий от параметра, который изменяется непрерывно:
.
При h
=0 имеем, что f
(0) – линия уровня функционала, проходящая через точку xk
. Для нахождения следующей линии уровня, более близкой к минимуму, будем выбирать h
таким образом, чтобы для данного xk
Это условие минимума по h
будем рассматривать как уравнение для получения hk
.
Решим его приближенно, т.к. ошибка в несколько процентов обычно не влияет на скорость сходимости. Отметим кстати, что число hk
всегда должно быть положительным. Для этого разложим функцию
в ряд Тейлора по h
в точке h
=0 и возьмем только линейную часть этого разложения
.
Подстановка линейной части в условие
, дает уравнение для приближенного определения
.
Решая построенное уравнение относительно h
, получим:
или
.
Таким образом, итерационная формула метода наискорейшего спуска имеет вид:
или
, где производные
вычислены в точке .
Метод наискорейшего спуска требует большего количества вычислений, чем другие методы первого порядка. Однако он обладает по сравнению с другими методами важным преимуществом, заключающемся в неизбежной сходимости процесса. При этом нужно помнить, что метод наискорейшего спуска может привести не к решению системы уравнений (2)
, а к значениям аргумента, дающим относительный экстремум функции
, т.е.
.
5. Сходимость методов решения нелинейных уравнений
Если метод сходится, то есть
, где
– точное решение
– k-тое приближение к точному решению, то итерационный процесс следовало бы закончить по достижению заданной погрешности
, где e
– заданная точность (погрешность).
Однако практически это условие выполнить нельзя, так как
неизвестно, тогда для окончания итерационного процесса можно воспользоваться неравенствами
, или
, где
и
– заданные величины.
При таком окончании итераций погрешность может возрасти по сравнению с
и, поэтому, чтобы не увеличивалась, величины
и
соответственно уменьшают или увеличивают число итераций.
Методы простой итерации, Зейделя, модифицированный метод Ньютона, метод наискорейшего спуска (см. [1]
, [2]
, [3]
, [4]
) являются методами первого порядка – это значит, что имеет место неравенство
, k
=1, 2, . . . , где
– константа, своя у каждого метода, зависящая от выбора начального приближения
, функции fi
, i
= 1, 2, . . . , n
, и их частных производных первого и второго порядков – точнее их оценок в некоторой окрестности искомого решения, которой принадлежит начальное приближение.
Метод Ньютона является методом второго порядка, то есть для него имеет место неравенство
, k
=1, 2, . . . , где
– константа, зависящая от тех же величин, что и константа
.
А теперь рассмотрим достаточные условия сходимости метода простой итерации и метода Ньютона.
Сходимость процесса простой итерации зависит от двух условий. Первое условие состоит в том, что какая-нибудь точка
должна оказаться близкой к исходному решению
. Степень необходимой близости зависит от функций j
1
,
j
2
, . . . , j
n
. Это требование не относится к системам линейных уравнений, для которых сходимость процесса простой итерации зависит только от второго условия.
Второе условие связано с матрицей, составленной из частных производных первого порядка функций j
1
,
j
2
, . . . , j
n
– матрицей Якоби
,
вычисленных в точке
.
В случае, когда рассматривается система линейных алгебраических уравнений, матрица M
состоит из постоянных чисел – коэффициентов, стоящих при неизвестных в правой части уравнения (3)
. В случае нелинейных уравнений элементы
матрицы M
зависят, вообще говоря, от
. Для сходимости процесса простой итерации достаточно, чтобы выполнялось неравенство:
для
из некоторой окрестности точного решения
, которой должно принадлежать начальное приближение .
Приведем также достаточные условия сходимости метода Ньютона для системы уравнений вида (2)
по норме
.
Предположим, что имеется начальное приближение
к искомому решению системы (2)
, функции
непрерывны и имеют непрерывные частные производные до второго порядка в шаре
, тогда, если выполнены условия:
1) Матрица Якоби
системы (2)
на начальном приближении имеет обратную
и известна оценка нормы обратной матрицы
,
2) Для всех точек шара
выполнено неравенство
при i
, j
= 1, 2, . . . , n
,
3) Выполнено неравенство
,
где L
– постоянная 0 £ L
£ 1,
4) Числа b
, N
, r
подчинены условию a
= nbNr
< 0,4, тогда система уравнений (2)
в шаре
имеет единственное решение, к которому сходятся последовательные приближения (8)
или (7’)
, (9’)
.
Для других методов условия сходимости имеют сложный вид, и мы отсылаем читателя к специальной литературе [1]
, [2]
, [3]
, [4]
.
6. Примерный перечень возможных исследований
1) Сравнение различных методов на экономичность при решении конкретной задачи:
· по числу операций на одной итерации;
· по числу итераций, необходимых для достижения заданной точности;
2) Зависимость числа итераций для достижения заданной точности:
· от выбора вида нормы;
· от выбора критерия окончания итерационного процесса по
или по невязке
;
· от выбора начального приближения;
· от погрешности задания коэффициентов в уравнении.
7. Контрольные вопросы
1) Понятие о нелинейных системах уравнений в Rn
.
2) Понятие приближенного и точного решения нелинейной системы уравнений.
3) Сущность графического метода отделения решения для системы двух нелинейных уравнений, каковы его преимущества и недостатки?
4) Сущность метода простой итерации и метода Зейделя. Каковы условия применимости метода простой итерации?
5) Сущность метода Ньютона и его модификации. Какова скорость сходимости метода Ньютона?
6) Сущность метода наискорейшего спуска. Как выбирается параметр спуска?
8. Порядок выполнения курсовой работы
1) Получить вариант задания, индивидуальный для каждого студента, у преподавателя, а именно:
Найти решение системы нелинейных уравнений в первой координатной четверти с номером – N
1
(см. варианты заданий п.10), применив для первого этапа уточнения метод с номером – N
2
, а для второго этапа уточнения метод с номером – N
3
, точность вычислений на первом этапе – EPS1Î[0.1 – 0.01], на втором этапе – EPS2 Î [0.1 - 0.0001], N
4
– номер нормы, I – номер параметра a
, J – номер параметра b
, начальное приближение выбрать произвольно или графически, aÎ(0,1).
2) Разработать обязательные для выполнения задания разделы данных методических указаний.
|