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

В.М.Волков

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

Теоретический минимум для студентов 5-го курса

Механико-математического факультета

(заочное отделение)

Минск 2009

В.М.Волков. Численные методы линейной алгебры.

Теоретический минимум для студентов 5-го курса механико-математического факультета

Численные методы алгебры играют ключевую роль в современных методах вычислений, поскольку практически все актуальные задачи современной вычислительной математики в конечном итоге замыкаются на решение задач алгебраического плана. Наиболее важные задачи алгебры, ассоциируемые с компьютерными вычислениями, состоят в решении систем алгебраических уравнений и сопутствующих им проблем (обращение матриц, проблемы собственных значений и собственных векторов, минимизации функционалов и т.п.).

Данное пособие дает краткое изложение основных концепций и алгоритмов численного анализа алгебраических задач, получивших широкое распространение в практике вычислений и давших начало современным вычислительным технологиям. Особенность данного пособия состоит в том, что рассмотренные алгоритмы приводятся в формате алгебраических операций над векторами и матричных без детализации структуры алгоритма на уровне поэлементной арифметики. Предполагается при этом, что практические занятия проводятся с использованием среды программирования Matlab, где отсутствует необходимость такой детализации.

Введение

Численные методы линейной алгебры, несмотря на их многообразие и кажущуюся на первый взгляд разобщенность, имеют общую алгоритмическую особенность – решение задачи может быть выражено последовательностью алгебраических операций над матрицами и векторами. Если использование алгоритма решения задачи позволяет получить решение за фиксированное число операций, то алгоритм называется прямым. Если метод основывается на повторяющейся вычислительной процедуре, каждый цикл которой дает более точное приближение искомого решения, то такой метод принято называть итерационным.

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