Методы решения СЛАУ. Отчет по лабораторной работе 1 Методы решения слау
 Скачать 1.93 Mb.
|
|
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)» (МГТУ им. Н.Э. Баумана) ФАКУЛЬТЕТ ИУ «Информатика и системы управления» КАФЕДРА ИУ1 «Системы автоматического управления» ОТЧЕТ по лабораторной работе №1 «Методы решения СЛАУ» по дисциплине «Методы вычислений» Выполнила: Санникова А.П. Группа: ИУ1 – 32Б Проверил: Бобков А.В. Работа выполнена: Отчет сдан: Оценка: Москва 2022 Оглавление 1. Метод Крамера 3 2. Метод Жордана – Гаусса 4 3. Метод решения с помощью разложения Холецкого 6 4. Метод Якоби 9 5. Метод Гаусса – Зейделя 11 6. Метод релаксаций 13 7. Метод градиентного спуска 14 Сравнение производительности методов 16 2 1. Метод Крамера Как правило, данный метод применяется только для тех систем, где по количеству неизвестных столько же, сколько и уравнений. Чтобы получилось решить уравнение, главный определитель матрицы не должен равняться нулю. Метод Крамера является универсальным и максимально точным, так как в нём присутствует малое количество операций деления. Вычислительная сложность: Т опр = О(N 3 ) и Т общ = О(N 4 ) - не может работать в реальном времени. Алгоритм: - вычислить главный определитель матрицы коэффициентов (не должен равняться 0); - вычислить определители матриц, получающихся подстановкой столбца свободных членов B на место i-го столбца в матрице коэффициентов A; - вычислить корни уравнения 𝑥 𝑖 = ∆ 𝑖 ∆ 3 2. Метод Жордана – Гаусса Этот метод является модификацией метода Гаусса — в отличие от исходного (метода Гаусса) метод Жордана-Гаусса позволяет решить СЛАУ в один этап (без использования прямого и обратного ходов). Он является также универсальным, но менее точным, чем другие методы из-за деления. Вычислительная сложность: Т = О(N 3 ) - может работать в реальном времени при маленьком N. Алгоритм: - составить расширенную матрицу из матрицы коэффициентов и столбца свободных членов и привести ее левую часть к диагональному виду; - правая часть расширенной матрицы и есть решение системы. 4 5 3. Метод решения с помощью разложения Холецкого Разложение Холецкого (метод квадратного корня) — представление симметричной положительно определённой матрицы A в виде A=LL Т , где L — нижняя треугольная матрица со строго положительными элементами на диагонали. Разложение Холецкого всегда существует и единственно для любой симметричной положительно определённой матрицы. Элементы матрицы L можно вычислить, начиная с верхнего левого угла матрицы, по формулам Тогда СЛАУ AX = B можно заменить системой {𝐿𝑌 = 𝐵 𝐿 𝑇 𝑋 = 𝑌 Метод квадратного корня является еще менее точным по своему определению и неуниверсальным. Вычислительная сложность: Т Y = О(N 2 ) и Т общ = О(N 3 ). 6 7 8 4. Метод Якоби Метод Якоби – это итерационный и численный метод решения СЛАУ. Суть его заключается в расщеплении матрицы коэффициентов А на диагональную D и остаток R. Тогда новое решение системы X t+1 можно найти, пользуясь менее точным решением X t : AX=B => X t+1 = D -1 [B – RX t ] Такой процесс должен быть остановлен при достижении минимальной ошибки вычислений. Ошибку можно косвенно оценить по приращению ε = 𝑖=1 𝑛 ∑ 𝑥 𝑖 * − 𝑥 𝑖 ( ) < ε 0 Метод Якоби не универсален, т.к. для его сходимости обязательно условие диагонального доминирования в матрице коэффициентов. Вычислительная сложность: Т = О(N 2 ) - быстрый. Хорошо распараллеливается. 9 10 5. Метод Гаусса – Зейделя Метод Гаусса-Зейделя – это итерационный и численный метод решения СЛАУ. Суть его заключается в расщеплении матрицы коэффициентов А на диагональную D, верхнюю треугольную R и нижнюю треугольную L. Тогда новое решение системы X t+1 можно найти, пользуясь решением предыдущей итерации X t : AX=B => X t+1 = (L + D) -1 [B – RX t ] Такой процесс должен быть остановлен при достижении минимальной ошибки вычислений. Ошибку можно косвенно оценить по приращению ε = 𝑖=1 𝑛 ∑ 𝑥 𝑖 * − 𝑥 𝑖 ( ) < ε 0 Метод Гаусса-Зейделя также не универсален, т.к. для его сходимости обязательно условие диагонального доминирования в матрице коэффициентов. Вычислительная сложность: Т = О(N 2 ) - быстрый (в 2-3 раза быстрее Якоби). Достижима любая точность. Не распараллеливается. 11 12 6. Метод релаксаций Метод верхних релаксаций – итерационный метод решения СЛАУ. Его суть заключается в следующем: после вычисления очередного приближения решения СЛАУ X t+1 , например, по Гауссу – Зейделю, эту компоненту дополнительно смещают на некоторую величину ω, что должно предоставить возможность как можно быстрее найти наиболее точное решение. X’ = X t + ω [X t+1 - X t ] Вычислительная сложность: Т = О(N 2 ) - быстрый. Достижима любая точность. Не распараллеливается. 13 7. Метод градиентного спуска Метод градиентного спуска позволяет прийти к более точному решению, зная необходимое направление (градиент ошибки). Шаг (скорость) оптимизации h в таком случае может быть константой, дробным (уменьшаться) или вычисленным наискорейшим спуском. Данный метод также нуждается в принудительной остановке. X * = X – h*gradE Этот метод универсален. Его скорость медленнее остальных итерационных методов, но быстрее, чем прямые. 14 15 Сравнение производительности методов Сравнить производительность методов можно, построив графики зависимости времени поиска решения от размерности матрицы коэффициентов. 16 17 18 |