- •Оглавление
- •Источники погрешностей при вычислениях по формулам.
- •1.1.Абсолютная и относительная погрешности. Оценки погрешностей
- •1.2. Границы значений числовых величин
- •1.3. Запись приближенных значений. Верные знаки
- •1.4. Округление. Погрешность округления. Первое правило подсчета верных знаков
- •Первое правило верных знаков
- •1.5. Линейные оценки погрешностей.
- •Линейные оценки погрешностей для функций нескольких переменных.
- •1.6. Метод границ
- •1.7. Правила подсчета верных знаков.
- •Контрольные вопросы
- •Литература
- •Тема 2. Численные методы решения уравнений с одним неизвестным
- •2.1. Постановка задачи. Метод последовательных приближений. Отделение корней
- •Отделение корней
- •Общая характеристика итерационных методов решения уравнений.
- •2.2. Метод половинного деления
- •2.3. Метод простой итерации
- •2.4. Метод касательных
- •2.5. Метод секущих
- •Оценка погрешности методов.
- •2.6. Комбинированный метод секущих и касательных
- •Контрольные вопросы
- •Литература
- •Тема 3. Численные методы решения систем уравнений
- •3.1. Постановка задачи
- •Общая характеристика численных методов решения систем линейных уравнений
- •3.2. Метод Гаусса
- •3.3. Метод простой итерации решения систем линейных уравнений
- •Контрольные вопросы
- •Литература
- •Тема 4. Интерполирование функций
- •4.1. Постановка задачи
- •4.2. Интерполяционный многочлен Лагранжа
- •Оценка погрешности интерполяционных формул
- •Контрольные вопросы
- •Литература
- •Тема 5. Наилучшее среднеквадратическое приближение
- •5.1. Аппроксимация функций методом наименьших квадратов
- •Нахождение приближающей функции в виде квадратного трехчлена
- •Контрольные вопросы
- •Литература
- •Тема 6. Численное интегрирование
- •6.1. Постановка задачи численного интегрирования. Квадратурные формулы Ньютона–Котеса
- •Формулы прямоугольников
- •Формула трапеций
- •Формула Симпсона (парабол)
- •6.2. Принцип Рунге оценки погрешностей
- •6.3. Статистический метод вычисления интегралов
- •I схема метода Монте–Карло
- •II схема метода Монте - Карло
- •Нахождение первообразной
- •Контрольные вопросы
- •Литература
- •Глоссарий
3.3. Метод простой итерации решения систем линейных уравнений
Систему уравнений ,(1) всегда можно преобразовать в виду (2), т.е.
Правые части системы (2) определяют отображение с помощью функцийF: (3). При этом. Задав каким - либо образом начальную точкуможно построить итерационную последовательность
Вопрос сходимости итерационной последовательности системы (2) решается несколько более сложно, чем скалярного уравнения x=f(x). Для этого приходится применять метод сжимающих отображений. Рассмотрим множество Х. Для любых двух точек x,y X введем расстояние (метрику) , таким образом, чтобы выполнились условия:
1)
2)
3) =
4)
Множество Х с введенной на нем метрикой называется метрическим пространством (Х, ). В метрическом пространстве можно определить понятие предела последовательности и фундаментальной последовательности.
Последовательность {} множества Х называется сходящейся к х элементу, если т.е..
Последовательность {} множества Х называется фундаментальной, если
В любом метрическом пространстве сходящаяся последовательность является фундаментальной. Обратное верно не всегда. Если в пространстве Х любая фундаментальная последовательность сходится, пространство Х называется полным метрическим пространством.
При решении методом простой итерации нужно: «погрузить» систему в подходящее полное метрическое пространство (т.е. подходящим образом ввести метрику в ).
Пусть отображение множества (Х,р) в себя. Пусть. ОтображениеF множества Х в себя называется - сжимающим, если . Точка хХ называетсянеподвижной относительно отображения F, если F(x)=x.
Применительно к системе (2) – неподвижная точка – это решение системы (при условии, что F – сжимающее отображение).
Существование неподвижной точки устанавливает теорема Банаха:
Если F - сжимающее отображение полного метрического пространства Х в себя, то существует единственная неподвижная точка хХ, такая, что х=F(x), причем итерационная последовательность сходится кx при любом начальном значении .
Оценка расстояния между приближением и неподвижной точкой оценивается по формулам
где – коэффициент из условия сжимаемости.
Таким образом если отображение F(х) является сжимающим отображением полного метрического пространства в себя, то решение системы (2) может быть найдено с любой степенью точности при любом выборе начального приближения .
Существует много способов введения метрики в пространстве , при этом пространство будет полным метрическим пространством. Можно рассматривать одну из следующих метрик:
1)
2)
3)
В каждой из них пространство будет полным, но следует учитывать, что отображение, задаваемое системой (3),должно быть сжимающим. Для этого достаточно, чтобы коэффициент из условия сжимающего отображения, рассчитываемый по формулам:
в пространстве
сумма абсолютных величин коэффициентов по строкам
в пространстве
сумма абсолютных величин коэффициентов по столбцам
в пространстве
был меньше 1.
Получим, например первое условие:
,
Таким образом, решение системы линейных уравнений вида (1) ,, Состоит из следующих этапов:
1) Привести систему (1) к виду , где все коэффициенты < 1 по модулю. Для этого нужно либо разделить каждое уравнение на наибольший коэффициент в нем и выразить итерационную переменную, либо использовать другие тождественные преобразования.
Пример:
x+2y+1=0 x+y+2=0
2y=-x-1 0,5x+0,5y+1=0
y=-0,5x-0,5 -0,5x-0,5y-1=0
x=0,5x-0,5y-1
2) Вычислить коэффициент и выбрать подходящую метрику.
3) Задать начальное приближение и построить итерационную последовательность, на каждом шаге оценивая расстояние между приближением и точным решением в выбранной метрике: .
4) Когда требуемая точность будет достигнута, определить невязку для найденного приближения.