Численные методы линейной алгебры

Задачи линейной алгебры, к которым относят решение систем линейных алгебраических уравнений (СЛАУ), обращение матриц, вычисление определителей, нахождение собственных значений и собственных векторов матриц являются классическими и наиболее исследованными задачами численных методов. К решению таких задач сводятся не только простейшие модели, учитывающие линейные взаимосвязи между различными факторами, но и многие более сложные математические модели, описываемые дифференциальными уравнениями в частных производных, или требующие аппроксимации экспериментальных данных некоторыми функциями, а также многие задачи оптимизации.

Для решения задач линейной алгебры в настоящее время разработаны весьма эффективные численные методы. Под термином эффективность в данном случае понимается возможность отыскания решения с заданной точностью за минимальное число арифметических и логических операций. Заметим, что скорость выполнения программ, реализующих численные методы линейной алгебры, используется как эталон при измерении производительности современных компьютеров. В частности, общепризнанный рейтинг производительности ЭВМ, публикуемый на сайте www.top500.org, за попадание в который борются все ведущие производители супер-ЭВМ, основан на измерении скорости выполнения программного пакета линейной алгебры – linpark.

Все численные методы линейной алгебры можно разделить на точные и итерационные.

Определение. Точными, или прямыми, называют методы, которые при отсутствии округлений дают точное решение задачи за конечное число арифметических и логических операций.

Нахождение корней СЛАУ по формулам Крамера в виде отношения определителей является примером такого точного метода. Данный метод, хотя и описан в каждом учебнике по линейной алгебре, никогда не используется при численном решении задач, так как требует для решения системы из n уравнений порядка n!n арифметических операций, ошибки округления в каждой из которых сказываются на получаемом результате. Его реализация на ЭВМ требует фантастического быстродействия и очень большой разрядности ячеек памяти при записи всех промежуточных вычислений.