Вариант 11: Сравнить МСГ и ЛОС для несимметричной матрицы. Факторизация LU(sq).
- Практическая работа №3 по предмету "Численные методы"
Скажем так, МСГ и ЛОС являются ещё более навороченными итерационными методами.
Например, особенностью МСГ является то, что он обязан сойтись не более, чем за N итераций метода. Происходит это потому, что в МСГ решение движется по смежным градиентам пространства (смежные == перпендикулярные). А в N-мерном пространстве может быть только N направлений движения (N нормалей). И в целом, если считать на бумажке, то так и выйдет, но так как мы не в сказке живём, а на компьютере, у нас есть погрешности вычислений, за счёт чего метод может сходиться дольше N операций (но не сильно дольше, только в совсем сложных ситуациях. Если сильно дольше - поздравляю, вы, как и я, наткнулись на невидимую ошибку).
ЛОС, по сравнению с МСГ, должен в процессе ещё и самокорректировать себя, поэтому с ним должно быть ещё меньше итераций (опять же, ни у кого из группы, в том числе и у себя, я не смог этого пронаблюдать. Магия какая-то).
Предобуславливание матрицы - довольно интересная тема, на самом деле. Ибо она помогает значительно сократить число итераций метода, повышая его производительность.
Как это работает? Цель предобуславливания - свести матрицу как можно ближе к диагональному виду, желательно единичному, таким образом превращая весь итерационный процесс решения СЛАУ в прямой метод. Понятное дело, не всегда это будет работать идеально, но при этом всё равно будет упрощать работу методов.
Здесь будет работать магия итерационных методов - LU-метод будет очень криво решать плохо обусловленные матрицы. И как раз-таки в этом случае, мы основное приближение решения получаем, решая LU-систему, а дальше требуемую нам точность мы добиваем за счёт итерационного процесса.
ЛОС оставил у меня на душе наиболее неприятные эмоции, ибо он вообще не любил у меня сходиться. Как оказалось, в том же Кирпиче это сказано, метод ЛОС периодически (каждые k итераций) нужно сбрасывать, пересчитывать все вспомогательные векторы относительно актуальных данных. Мем в том, что на одних и тех же входных данных, на визуально идентичных программах, метод умудряется считать совершенно по-разному (ну, очевидно, различия есть, но заметить их без лупы невозможно и у меня ещё не удавалось. Спишу на усталость).
Где-то сразу за ней начнётся курсовая работа. И да, одним из её моментов будет как раз-таки применение одного из этих двух методов. И будет очень хорошо, если вы заранее позаботитесь и напишите НЕ одноразовую программу🙃.
Алгоритмы МСГ и ЛОС реализованы в файлах, лежащих в каталоге "chm_3)" (тут тоже в названии проекта закосячил, признаюсь). Основные модули программы:
SparseMatrix- модуль описания класса разреженной строчно-столбцовой матрицы. Все методы продублированы так, чтобы можно было использовать их без выделения новой памяти и с её выделением.LU- модуль описания класса LU-разложения произвольной матрицыSparseMatrix. Опять же все методы продублированы с выделением новой памяти или с использованием уже выделенной переданной в неё.IterSolvers- модуль описания пространства имён, связанного с трёхшаговыми методами решения СЛАУ.
Как всем этим пользоваться для 6 вариантов выбора решателя - расписано в модуле main.cpp.
Множество готовых наборов входных данных лежат в папке "chm_3)/iofiles".
В целом, ничего нового, генератор Гильбертовых матриц был вытянут из 1 практической работы, лишь немного изменён под текущий формат хранения данных.
Да, в один момент меня это так задолбало, что я решил покрыть весь код unit-тестами. Не смог, времени перед курсачом уже не оставалось, забил. Может, в будущем я всё-таки вернусь и закончу начатое, всё-таки курсач хочется допиливать с рабочими трёхшаговыми методами.