Akademik

численные методы - раздел вычислительной математики, посвященный математич. описанию и исследованию процессов численного решения задач линейной алгебры.

Среди задач Л. а. наибольшее значение имеют две: решение системы линейных алгебраич. уравнений и определение собственных значений и собственных векторов матрицы. Другие часто встречающиеся задачи: обращение матрицы, вычисление определителя и нахождение корней алгебраич. многочлена, как правило, не имеют самостоятельного значения в Л. а. и носят вспомогательный характер при решении основных задач Л. а.

Любой численный метод в Л. а. можно рассматривать как нек-рую последовательность выполнения арифметич. операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметич. операций, то такой метод наз. прямым. В противоположном случае численный метод наз. итерационным.

Прямые методы решения системы линейных алгебраических уравнений. Пусть дана система

с матрицей системы Аи правой частью b. Г. сли матрица Аневырожденная, то решение дается формулой есть матрица, обратная к матрице А. Основная идея прямых методов заключается в преобразовании системы (1) в такую эквивалентную систему, для к-рой матрица системы легко обращается и, следовательно, легко находится решение исходной системы. Пусть обе части равенства (1) умножены слева на невырожденные матрицы Тогда новая система

эквивалентна системе (1). При этом матрицы L;всегда можно подобрать такими, что матрица системы (2) будет достаточно простой, напр. треугольной, диагональной или унитарной. В этом случае легко вычисляются

Одним из первых прямых методов является Гаусса метод. Он использует левые треугольные матрицы L_i и позволяет привести исходную систему уравнений к системе с правой треугольной матрицей. Этот метод легко реализуется на ЭВМ, его схема с выбором главного элемента позволяет решать системы с произвольной матрицей, а компактная схема - получать результаты с повышенной точностью за счет накопления скалярных произведений. Среди прямых методов, применяемых на практике, метод Гаусса требует минимального объема вычислительной работы.

Непосредственно к методу Гаусса примыкают метод Жордана и его модификация - метод оптимального исключения (см. [2]). Эти методы используют треугольные матрицы L_i как левые, так и правые и позволяют привести исходную систему к системе с диагональной матрицей. По своим характеристикам оба метода мало чем отличаются от метода Гаусса, но второй позволяет решать системы вдвое большего порядка при одной и той же памяти ЭВМ.

Перечисленные методы входят в группу т. н. методов исключения. Это название объясняется тем, что при каждом умножении на матрицу L_i в матрице системы исключается один или несколько элементов. Исключение можно производить не только с помощью треугольных матриц, но и с помощью унитарных. Различные модификации методов исключения по существу связаны с разложением матрицы системы (1) в произведение двух треугольных или треугольной и унитарной матриц.

Некоторые методы, такие как окаймления метод, пополнения метод, не являются методами исключения, хотя и близки к методу Гаусса.

Большое распространение получили методы, основанные на построении вспомогательной системы векторов, так или иначе связанных с матрицей исходной системы и ортогональных в нек-рой метрике. Одним из первых методов этой группы был метод ортогонализации строк. Матрицы L_i в нем - левые треугольные, матрица системы (2) - унитарная. Методы, основанные на ортогонализации, обладают многими достоинствами, но чувствительны к влиянию ошибок округления. На основе развития методов типа ортогонализации был создан весьма эффективный (при решении нек-рых систем с разреженными матрицами) сопряженных направлений метод (см. [9], [10]).

Прямые методы определения собственных значений и собственных векторов матрицы. Пусть для матрицы Атребуется определить собственное значение l и собственный вектор х, т. е. решить уравнение

При замене х=Су, где С - невырожденная матрица, уравнение (3) перейдет в уравнение при Прямые методы решения данной задачи состоят в том, что с помощью конечного числа подобных преобразований исходная матрица Априводится к матрице Внастолько простого вида, чтобы для нее легко находились коэффициенты характеристич. многочлена и собственные векторы. При этом собственные значения находятся как корни характеристич. многочлена каким-либо из известных методов. Численные методы перехода от матрицы Ак матрице Впо существу мало чем отличаются от численных методов преобразования системы (1) в систему (2). Известно много методов подобного типа (методы Крылова, Данилевского, Хессенберга и т. д., см. [1]), однако они не нашли широкого применения на практике в силу значительной численной неустойчивости (см. [3]).

Различают полную проблему собственных значений, когда ищутся все собственные значения, и частичную проблему, когда отыскивают нек-рые из них; последняя задача более типична в случае сеточных задач, возникающих при аппроксимации дифференциальных и интегральных уравнений.

Итерационные методы решения системы линейных алгебраических уравнений. Эти методы дают решение системы (1) в виде предела последовательности нек-рых векторов; построение их осуществляется посредством единообразного процесса, наз. процессом и т е р а ц и й. Основные итерационные процессы для решения системы (1) могут быть описаны посредством единообразного процесса следующей общей схемой. Строится последовательность векторов по рекуррентным формулам

где - нек-рая последовательность матриц, x⁽⁰⁾ - начальное приближение, вообще говоря, произвольное. Различный выбор последовательности матриц H^(k) приводит к различным итерационным процессам.

Простейшими итерационными процессами являются стационарные процессы, в к-рых матрицы H^(k) не зависят от номера шага А; их также наз. методами простой итерации (см. [5]). Если последовательность H^(k) периодична, то процесс наз. циклическим. Всякий циклич. процесс может быть преобразован в стационарный, но обычно такое преобразование усложняет метод. Нестационарные процессы, в частности циклические, используются для ускорения сходимости итерационных процессов (см. [5], [6]). Среди методов ускорения сходимости особое место занимают методы, использующие многочлены Чебышева (см. [5], [6]) и сопряженные направления (см. [10]).

Выбор матрицы H для стационарного процесса и матриц H^(k) для нестационарного может осуществляться различными способами. Возможно построение матриц H^(k) таким образом, чтобы итерационный процесс сходился к решению и по возможности быстро для широкого класса систем уравнений (см. [5]). Возможен и противоположный подход, когда при построении матриц H^(k) максимально используются частные особенности данной системы для получения итерационного процесса с наибольшей скоростью сходимости (см. [6]). Второй способ построения матриц H^(k) является наиболее распространенным.

Одним из наиболее распространенных принципов построения итерационных процессов является принцип релаксации (см. Релаксации методы). В этом случае матрицы H^(k) выбираются из заранее описанного класса матриц так, чтобы на каждом шаге процесса уменьшалась какая-либо величина, характеризующая точность решения системы. Среди релаксационных методов наиболее разработаны координатные и градиентные методы. В координатных методах матрицы H^(k) подобраны так, что на каждом шаге меняются одна или несколько компонент последовательных приближений. О точности приближенного решения хчаще всего судят по величине вектора невязки r=Ах-b.

В случае стационарных итерационных методов главный член погрешности можно оценить также с помощью d² -процесса (см. [5]).

Среди других итерационных методов можно отметить простой итерации метод, переменных направлений метод, методы полной и неполной релаксации и т. д. (см. [1], [6], [10]). Как правило, итерационные методы удобны для реализации на ЭВМ, однако в отличие от прямых методов они чаще всего обладают весьма ограниченной областью применения. В области же их применения итерационные методы нередко существенно превосходят прямые методы по объему вычислений. Поэтому вопрос сравнения прямых и итерационных методов может быть решен лишь при детальном изучении свойств конкретной системы. Наибольшее распространение нашли итерационные методы для решения систем, возникающих при разностной аппроксимации дифференциальных уравнений (см. [5], [6]).

Итерационные методы решения полной проблемы собственных значений. В итерационных методах собственные значения вычисляются как пределы нек-рых числовых последовательностей без предварительного определения коэффициентов характеристич. многочлена. Как правило, при этом одновременно находятся и собственные векторы или нек-рые другие векторы, связанные с собственными простыми соотношениями. Большинство итерационных методов менее чувствительны к ошибкам округления, чем прямые, но значительно более трудоемки. Развитие этих методов и их применение в практике вычислений стало возможным лишь после создания ЭВМ.

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

Метод вращений очень прост, легко реализуется на ЭВМ и всегда сходится. Независимо от расположения

собственных значений он обладает асимптотически квадратичной сходимостью. Наличие кратных и близких собственных значений не только не замедляет сходимость метода, но, напротив, приводит к ее ускорению. Метод вращений устойчив к влиянию ошибок округления результатов промежуточных вычислений. Свойства этого метода послужили причиной его распространения на решение полной проблемы матриц более общего вида. Без существенных изменений метод вращений переносится на эрмитовы и косоэрмитовы матрицы. Незначительное его изменение позволяет с успехом решать полную проблему для матриц А *А и АА* одновременно, не вычисляя сами произведения матриц. Эффективное распространение этого метода на произвольные матрицы простой структуры реализуется обобщенным методом вращении.

Среди итерационных методов решения полной проблемы собственных значений значительную группу составляют степенные методы. Большинство их вычислительных алгоритмов укладывается в следующие схемы:

Здесь на каждом шаге матрица, стоящая в левой части равенства, раскладывается в произведение двух матриц. Пусть одна из них треугольная, а вторая унитарная или треугольная другого наименования. Тогда при нек-рых дополнительных предположениях матрицы сходятся к квазитреугольной матрице, подобной матрице А. Как правило, порядки диагональных клеток квазитреугольной матрицы невелики, поэтому полная проблема собственных значений для предельной матрицы решается достаточно просто.

Известно несколько методов такого типа. Одним из лучших среди них является QR-a л г о р и т м (см. [7]). Вычислительные схемы степенных методов во многом совпадают с вычислительными схемами решения систем уравнений прямыми методами.

Исследование и классификация численных методов. Огромное количество численных методов Л. а. ставит актуальной задачей не столько создание новых, сколько исследование и классификацию существующих методов (одна из самых полных классификаций методов с точки зрения их математич. построения содержится в монографии [1]; описанию методов с точки зрения возможности их реализации на ЭВМ посвящены монографии [2], [3], [7]).

Первые фундаментальные работы по анализу устойчивости и ошибок округления в численных методах решения задач Л, а. появились лишь в 1947-48 и посвящены исследованию обращения матриц и решению систем уравнений методами типа Гаусса. Практич. ценность этих результатов была невелика. Существенный сдвиг в изучении данного вопроса произошел в середине 60-х гг. (см. [3]), когда был сделан решающий шаг к анализу и оценке эквивалентных возмущений. Реально вычисленное решение нек-рой задачи стало рассматриваться как точное решение той же задачи, но с возмущенными входными данными. Это возмущение, наз. эквивалентным, полностью характеризует влияние ошибок округления. Исследовано большое кол-во методов с точки зрения мажорантной оценки нормы эквивалентного возмущения (см. [3], [7]).

При фиксированном вычислительном алгоритме и способе округления вся совокупность ошибок округления является однозначной векторной функцией зависящей от числа разрядов t, с к-рыми ведется счет, и от входных данных А. Главный член

функции при не имеет сколько-нибудь приемлемого явного выражения. Однако весьма эффективным оказалось исследование на классе случайно заданных входных данных. Оно показало, что наиболее вероятное значение отклонения вычисленного решения от точного за счет ошибок округления существенно меньше, чем максимально возможное (см. [7]).

Анализ влияния ошибок округления показал, что между лучшими методами нет принципиальной разницы с точки зрения устойчивости к ошибкам округления. Этот вывод заставляет по-новому взглянуть на проблему выбора того или иного численного метода в практич. деятельности вычислителя. Создание мощных ЭВМ существенно ослабило значение различия между методами в таких характеристиках, как объем требуемой памяти ЭВМ и количество арифметич. операций, и привело к возросшим требованиям на гарантию точности решения. В этих условиях наиболее предпочтительными становятся те методы, к-рые, не очень отличаясь от лучших по скорости и удобству реализации на ЭВМ, позволяют решать широкий класс задач как хорошо, так и плохо обусловленных и давать при этом оценку точности вычисленного решения.

Классификация и сравнение численных методов, о к-рых говорилось выше, относятся в основном к тому случаю, когда вся совокупность входных данных целиком помещается в оперативную память ЭВМ. Однако особый интерес представляют два крайних случая - решение задач Л. а. на малых и сверхмощных ЭВМ. Решение задач на таких ЭВМ имеет свою специфику. В первом случае - это малая память, ограниченная разрядная сетка и счет в режиме фиксированной запятой, во втором - наличие мультипрограммного режима работы ЭВМ, режима разделения времени и т. д.

Лит.:[1] Фаддеев Д. К., Фаддеева Д. Н., Вычислительные методы линейной алгебры, 2 изд., М.- Л., 1963; [2] Воеводин В. В., Численные методы алгебры. Теория и алгорифмы, М., 1966; [3] У и л к и н с о н Дж.-Х., Алгебраическая проблема собственных значений, пер. с англ., М., 1970; [4] Воеводин В. В., "Вестн. Моск. ун-та. Матем., механ.", 1970, № 2, с. 69-82; [5] Бахвалов Н. С., Численные методы, 2 изд., М., 1975; [6] Самарский А. А., Николаев Е. С., Методы решения сеточных уравнений, М., 1978; [7] В о е в о д и н В. В., Вычислительные основы линейной алгебры, М., 1977; [8] Фаддеева В. Н. [и др.], Вычислительные методы линейной алгебры. Библиографический указатель. 1828-1974 гг., Новосиб., 1976; [9] Воеводин В. В., Линейная алгебра,2 изд., М., 1980: [10] М а р ч у к Г. И., Кузнецов Ю. А., Итерационные методы и квадратичные функционалы, Новосиб., 1972. В. В. Воеводин.