Условие сходимости метода простых итераций
Понятие«вычислительная задача». Типы вычислительных задач и их постановка.
Решение задачи с помощью компьютера - это процесс автоматического преобразования исходной информации (исходных данных) в искомый результат в соответствии с заданной последовательностью выполнения действий, называемой алгоритмом. Вычислительные задачи связаны с вычислением в традиционном (арифметическом) смысле этого слова неизвестного значения информационного объекта (переменной, функции и т.д.). Основными элементарными операциями, выполняемыми при решении таких задач, являются арифметические операции сложения, вычитания, умножения, деления, возведения в степень и т.д. В постановке вычислительной задачи выделяют три обязательных элемента: условие задачи, известные данные (исходные данные) и неизвестное (неизвестные). Условие задачи представляет собой явно или неявно выраженное соотношение между данными и неизвестными задачи.
Условия корректности вычислительной задачи.
Корректность. Определим вначале понятие устойчивости решения.
Решение задачи y* называется устойчивым по исходным данным x*, если оно зависит от исходных данных непрерывным образом. Это означает, что малому изменению исходных данных соответствует малое изменение решения. Строго говоря, для любого e > 0 существует d = d(e) > 0 такое, что всякому исходному данному x*, удовлетворяющему условию |x - x*| < d, соответствует приближенное решение y*, для которого |y – y*| < e.
|
|
|
Говорят, что задача поставлена корректно, если выполнены следующие три условия:
1. Решение существует при любых допустимых исходных данных.
2. Это решение единственно.
3. Это решение устойчиво по отношению к малым изменениям исходных данных.
Если хотя бы одно из этих условий не выполнено, задача называется некорректной.
Метод Гаусса решения систем линейных алгебраических уравнений: класс метода, прямой и обратный ходы, оценка трудоемкости.
Метод последовательного исключения неизвестных Гаусса является одним из универсальных, точных и прямых методов, позволяющих за конечное количество действий получить точное решение системы.
Решение по этому методу выполняется в два хода: прямой и обратный.
При прямом ходе исходная система уравнений:
приводится к эквивалентной системе с треугольной матрицей коэффициентов:
При обратном – из эквивалентной системы идёт последовательное, начиная с конца, определение неизвестных xj, j= n, n – 1, …, 1 по следующим рекуррентным формулам:
– при j= n получаем 
– при j=n – 1, n – 2, … , 1 получаем 
Трудоёмкость метода Гаусса
Количество действий прямого хода:
|
|
|
Количество действий обратного хода:
.
Суммарное количество действий:
Здесь n – количество уравнений (порядок) системы.
При n = 3
Метод простых итераций решения систем линейных алгебраических уравнений: класс метода, оценка трудоемкости, условие сходимости, получение начального приближения, алгоритм решения, условие окончания.
Это приближённый метод. Он позволяет получить решение сис-темы линейных алгебраических уравнений с погрешностью, не превышающей заданную допустимую величину ε, за ограниченное количество итераций.
Имеем исходную систему уравнений:
(1.5)
Запишем систему (1.5) в матричной форме:
AX = B,
где A (n´n) – матрица коэффициентов aij;
B(n) – вектор правых частей bi;
X(n) – вектор решений xj.
Можно представить исходную систему матричным уравнением
AX – B = 0
или в развёрнутой матричной форме
Вектор-столбец в правой части с нулевыми значениями элементов получается, когда векторX есть точное решение системы. В противном случае получим вектор-«невязок»
Обозначим через Z вектор приближённых значений решения системы. Вначале это будет нулевое приближение – вектор Z(0). В качестве начального приближения решения системы можно брать 
.
|
|
|
При подстановке в систему (1.8) на место X вектора Z(0) получим:
(1.9)
где 
– вектор-«невязок» начального (нулевого) приближения относительно точного решения.
Цель и суть метода простых итераций – сведение к нулю «невязок» в решении системы (1.9). Практически стремятся к выполнению условия
где S – номер итерации, S = 0, 1, 2, …
Общая формула
где j – номер слагаемого скалярного произведения i-той строки матрицы A на вектор Z.
Условие сходимости метода простых итераций
Метод простых итераций сходится при условии, что диагональные коэффициенты матрицы A исходной системы по абсолютной величине больше суммы абсолютных величин других коэффициентов в своей строке:
Дата добавления: 2018-04-15; просмотров: 3355; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!