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