26. Численные методы решение алгебраических уравнений: постановка задачи, метод простых итераций.
Предположим, что уравнение (1) при помощи некоторых тождественных преобразований приведено к виду (2):
(1)
(2)
Пусть
известно начальное приближение к корню
,
тогда подставим его в правую часть
уравнения (2) и получим новое приближение:
(3)
Затем
аналогичным образом получим
и т.д.:
(4)
Заметим:
тот факт, что
корень уравнения
,
означает, что
есть
абсцисса точки пересечения графика
с
прямой
.
Необходимо установить, при каких условиях итерационный процесс будет сходиться к корню уравнения .
Рассмотрим процесс графически (рисунок 1).
Рисунок 1
Из
графиков видно, что при
и
при
возможны
как сходящиеся, так и расходящиеся
итерационные процессы.
Скорость
сходимости зависит от абсолютной
величины производной функции
.
Чем меньше
вблизи корня, тем быстрее сходится
процесс.
Установим теперь критерий сходимости математически.
Будем считать, что в итерационной формуле (4)
(5)
где
,
- отклонения k
и k+1приближения
к корню. Если процесс уточнения
осуществляется вблизи корня
,
то функцию
можно
приближенно представить двумя членами
ряда Тейлора. Тогда итерационная формула
(4) примет вид (6):
(6)
но
так как
является
корнем уравнения, то
и,
следовательно (7),
(7)
Для того чтобы итерационный процесс был сходящимся, необходимо выполнить условие (8)
(8)
или
Переход
от уравнения (1) к уравнению (2) можно
осуществить разными способами в
зависимости от вида функции
.
При таком переходе необходимо построить
функцию
так,
чтобы выполнялось условие сходимости
(8).Рассмотрим один из общих алгоритмов
перехода от уравнения (1) к уравнению
(2).Умножим левую и правую части уравнения
(1) на произвольную константу
и
добавим к обеим частям неизвестное
.
При этом корни исходного уравнения не
изменятся (9):
(9)
Введем
обозначение
(10)
и перейдем от соотношения (9) к уравнению (2).
Произвольный
выбор константы
позволит
обеспечить выполнение условия сходимости
(8). Желательно выбрать величину
такой,
чтобы
,
тогда сходимость итерационного процесса
будет двухсторонней. В этом случае в
наиболее простом виде можно представить
критерий окончания итерационного
процесса.
(11)
где
-
заданная абсолютная погрешность
вычисления корня. Если функция
выбрана
в виде (1.33), то производная по
от
этой функции будет
(12).Наибольшую скорость сходимости
получим при
,
тогда
и
итерационная формула (4) переходит в
формулу Ньютона (13)
27. Численные методы решения систем линейных уравнений (слау): проверка корректности постановки задачи.
Исследование
устойчивость задачи
сводится к исследованию зависимости
ее решения от правых частей
и элементов
матрицы А. Для того чтобы можно было
говорить о непрерывной зависимости
вектора решений от некоторых параметров,
необходимо на множестве
-
мерных векторов принадлежащих линейному
пространству H,
ввести метрику.
В
линейной алгебре предлагается определение
множества метрик
норма
из которого легко получить наиболее
часто используемые метрики
при
р=1,
,
при
,
,
при
,
.
Подчиненные
нормы матриц определяемые как
, соответственно запишутся в следующем
виде:
,
,
.
Обычно рассматривают два вида устойчивости решения системы (1):первый по правым частям, второй по коэффициентам системы(1) и по правым частям..
Наряду с исходной системой (1) рассмотрим систему с «возмущенными» правыми частями
,
где
возмущенная правая часть системы, а
возмущенное решение.
Можно получить оценку, выражающую зависимость относительной погрешности решения от относительной погрешности правых частей
,
где
число обусловленности матрицы А ( в
современной литературе это число
обозначают как
)
Если число обусловленности велико (
),
то говорят, что матрица А плохо обусловлена.
В этом случае малые возмущения правых
частей системы (1), вызванные либо
неточностью задания исходных данных,
либо вызванные погрешностями вычисления
существенно влияют на решение системы.
Грубо говоря если погрешность правых
частей
,
то погрешность решения будет
.
Более подробно о свойствах числа
обусловленности и оценка его величины
можно прочитать в [3].
Если возмущение внесено в матрицу А, то для относительных возмущений решения запишем
.