Итерационные методы представляют собой методы последовательных приближений. Процесс итераций должен быть построен таким образом, чтобы с ростом числа шагов, получаемые…
Итерационные методы представляют собой методы последовательных приближений. Процесс итераций должен быть построен таким образом, чтобы с ростом числа шагов, получаемые приближённые значения корней сходились к точному решению. Исходные данные, т.е. коэффициенты при неизвестных и свободные члены, в практических задачах часто обладают неустранимой погрешностью. В этой связи важным достоинством итерационных методов является то, что можно заранее задать точность искомого решения. Главный же их недостаток - для каждого рекуррентного процесса необходимо исследование условий его сходимости. СЛАУ- Системой линейных алгебраических уравнений называется система вида, где каждое уравнение является линейным относительно неизвестных. В матричной форме она записывается как произведение матрицы коэффициентов на вектор неизвестных равно вектору правых частей. Точными называются методы, которые позволяют получить решение за конечное число арифметических операций. Примерами служат метод Гаусса, метод Крамера, метод обратной матрицы. Приближённые (итерационные) методы Итерационными называются методы, в которых строится бесконечная последовательность приближений, сходящаяся к точному решению. Вычисления прекращают, когда достигнута заданная точность. Итерационный процесс Итерационным процессом называется правило, по которому каждое следующее приближение вычисляется через предыдущее. Процесс записывается в виде формулы, где новое значение равно некоторому преобразованию старого значения. Начальное приближение Начальным приближением называется вектор, с которого начинается итерационный процесс. Чаще всего выбирают нулевой вектор, но иногда используют другие значения, если о решении есть дополнительная информация. Сходимость итерационного процесса Итерационный процесс называется сходящимся, если последовательность приближений стремится к точному решению при неограниченном увеличении числа шагов. Метод Якоби Методом Якоби называется итерационный метод, в котором каждое неизвестное на новом шаге вычисляется из соответствующего уравнения с использованием всех остальных неизвестных с предыдущего шага. Описание метода В методе Якоби из каждого уравнения выражается диагональное неизвестное. Для вычисления нового значения берутся все остальные неизвестные с предыдущей итерации. Таким образом, для перехода от одного приближения к следующему необходимо сохранять все значения предыдущего шага. Достаточное условие сходимости Метод Якоби сходится, если матрица системы обладает свойством диагонального преобладания. Это означает, что для каждой строки модуль диагонального элемента больше суммы модулей всех остальных элементов этой строки. Метод Гаусса–Зейделя Методом Гаусса–Зейделя называется итерационный метод, в котором каждое неизвестное на новом шаге вычисляется с использованием уже обновлённых значений предыдущих неизвестных на этом же шаге. Метод релаксации Методом релаксации называется итерационный метод, в котором вводится дополнительный параметр для ускорения сходимости. напиши кратко но отражая суть Вопросы для самопроверки Дайте определение итерационного метода решения систем линейных уравнений. Чем он отличается от точного метода? Сформулируйте достаточное условие сходимости итерационного процесса. Какую роль при этом играет норма матрицы перехода? В чём заключается основная идея метода Якоби? Как вычисляется новое приближение для неизвестного? В чём заключается основная идея метода Гаусса–Зейделя? Чем его вычислительная схема отличается от метода Якоби? Почему метод Гаусса–Зейделя обычно сходится быстрее метода Якоби? Какое преимущество по памяти он даёт? Что такое метод релаксации? Какую роль играет параметр релаксации и как его выбор влияет на сходимость? Сформулируйте условие диагонального преобладания. Почему это условие гарантирует сходимость методов Якоби и Гаусса–Зейделя? Назовите три основных критерия остановки итерационного процесса. В чём недостатки каждого из них? В каких случаях предпочтительнее использовать итерационные методы, а в каких — точные методы? Укажите основные критерии выбора.
- Итерационный метод и точный метод
- Итерационный метод: строится бесконечная последовательность приближений x^(k), которая стремится к точному решению Ax = b при бесконечном числе шагов; удобно для больших и разреженных систем.
- Точный метод: дает решение в finitely-м количестве арифметических операций (например, Гаусса, формула Крамера, обратная матрица).
- Условие сходимости и роль нормы переходной матрицы
- Сходимость обеспечивается, если для переходной матрицы B в виде x^(k+1) = B x^(k) + d выполняется ρ(B) < 1 (спектральный радиус).
- Роль нормы: достаточное условие — ||B|| < 1 в какой-либо норме; если это выполняется, то сходимость гарантирована (но не обязательно необходима). Диагональное преобладание обеспечивает такое условие через нормы.
- Основная идея метода Якоби
- Каждый неизвестный на шаге k+1 вычисляется из соответствующего уравнения, используя все остальные неизвестные из шага k: x_i^(k+1) = (b_i − ∑{j≠i} a{ij} x_j^(k)) / a_{ii}. Все x_i^(k+1) вычисляются параллельно.
- Основная идея метода Гаусса–Зейделя
- Каждое новое значение x_i^(k+1) вычисляется с использованием недавно полученных значений: x_i^(k+1) = (b_i − ∑{j<i} a_{ij} x_j^(k+1) − ∑_{j>i} a{ij} x_j^(k)) / a_{ii}. Обновления последовательны внутри шага.
- Почему Гаусса–Зейделя быстрее Якоби и память
- GS обычно сходится быстрее, т.к. использует свежие значения сразу же в расчёте последующих компонент.
- Память: GS может работать в одну векторную память (in-place), в то время как Якоби требует две копии векторов (старого и нового).
- Метод релаксации
- Вводится параметр релаксации ω: x^(k+1) = x^(k) + ω (x^(k+1,_GS) − x^(k)).
- Роль ω: ускоряет сходимость при подходящем выборе (часто 1 < ω < 2 для ускорения над Гауссом–Зейделем, но слишком большое ω может привести к расходимости). Выбор ω зависит от задачи.
- Условие диагонального преобладания и его роль
- Условие: для каждой строки i выполняется ∣a_ii∣ > ∑_{j≠i} ∣a_ij∣.
- Обоснование: обеспечивает уменьшение нормы итерационной матрицы (например, ||B||_∞ < 1), следовательно ρ(B) < 1 и сходимость методов Якоби и Гаусса–Зейделя.
- Три основных критерия остановки и их недостатки
- Абсолютная/относительная норма остатка: ||b − Ax^k|| ≤ tol. Недостаток: при плохой обусловленности остаток может плохо отражать реальную погрешность.
- Норма изменения решения: ||x^(k+1) − x^k|| ≤ tol. Недостаток: может «застревать» в малых шагах даже при сущеочной погрешности.
- Максимальное число итераций: k ≤ maxIter. Недостаток: можно досрочно остановиться до достижения нормы; не гарантирует реального решения.
- Когда предпочтительны итерационные или точные методы? Основные критерии выбора
- Предпочтение итерационных: очень крупные или разреженные системы, ограниченная память, требуется приближённое решение за ограниченное время, множество правых частей или необходимость частых пересчётов без полного разложения матрицы.
- Предпочтение точных методов: небольшие или плотные системы, нужна высокая точность за раз, хорошо обусловленная система, возможность заранее разложить LU и многократно использовать результат.
