ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ СИСТЕМ УРАВНЕНИЙ СПОСОБЫ РЕШЕНИЯ

— совокупность способов, обеспечивающих нахождение вектора из системы уравнений

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

Рассмотрим Л. а. с. у. с. р. в зависимости от характерных для практики различий в объеме и структуре исходных данных.

1. Л. а. с. (1) имеет матрицу, близкую к вырожденной, а именно: изменение элементов матрицы А в пределах точности их задания может привести к чисто вырожденной матрице . Такие задачи наз. некорректно поставленными. На практике указанные задачи возникают чаще всего тогда, когда реальный процесс описывается системой ур-ний с чисто вырожденной матрицей, но в результате неизбежных погрешностей измерений полученная прибл. система (1) имеет матрицу, уже отличную от чисто вырожденной. Возможен также случай, когда , а прибл. вектор у не удовлетворяет условиям разрешимости. Иными словами, такая система не имеет «классического» матем. решения. Для построения решения некорректно поставленных задач, даже если они разрешимы, оказываются абсолютно неприемлемыми численные методы, дающие математически точные решения заданной системы (1). Это объясняется тем, что в данной ситуации решение системы весьма чувствительно к малым изменениям исходных данных и математически точное решение «возмущенной» системы (1) может оказаться далеким от состояния реального процесса. В этом случае для построения решения следует использовать методы регуляризации для решения вырожденных л. а. с. (см. Некорректно поставленных задач способы решения). Один из методов регуляризации состоит в том, что вместо системы (1) решается всегда разрешимая система

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

2. Известно, что возможные вариации заданной невырожденной матрицы А не могут превратить ее в вырожденную матрицу если выполняется условие

в любой из норм. В частности, в спектральной норме это означает, что норма возмущения должна быть меньше миним. модуля собственного значения матрицы (в случае симметричной 4) или меньше квадратного корня из миним. собственного значения матрицы (для произвольной матрицы А). Иными словами, выполнение условия (3) гарантирует выход за пределы 1-го случая. Однако это условие ни в коем случае не обеспечивает близости решений истинной, но не известной нам системы и заданной прибл. системы Даже точные решения этих двух систем при выполнении условия (3) могут весьма сильно отличаться друг от друга. Ф-ла

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

Предполагая случайными нормально распределенными величинами (см. Нормальное распределение), получаем, что в рамках линейной теории также нормально распределено и область его возможных значений при заданной вероятности точно совпадает с соответствующим гипер-эллипсоидом рассеивания. При численном решении л. а. с. (1) достаточно попасть в любую точку этого эллипсоида, и это при больших его размерах может облегчить решение задачи, но при этом само решение может потерять практический смысл. В этом случае приходится иметь дело с т. н. плохо обусловленной системой, решение которой имеет лишь устойчивую проекцию на подпространство, образованное собственными векторами матрицы 44, соответствующими большим собственным значениям. Поэтому, если нельзя переформулировать задачу так, чтобы получить достаточно хорошо обусловленную систему, то для заданной плохо обусловленной задачи имеет смысл находить лишь упомянутую устойчивую проекцию. Один из способов отыскания этой проекции может быть основан на предварительном отыскании необходимых собственных чисел и векторов (см. Собственных значений и собственных векторов матриц способы вычисления), после чего и искомая проекция где выбранные большие собственные значения, единичные векторы в направлении взаимно-ортогональных осей. Нередко по практическому смыслу задачи нас устраивает любое которое дает достаточно малое значение Если таково, что то и мы вправе выбрать б, минимизирующее полученную оценку. Функция от является всегда выпуклой и квадратической. На этом основаны многие способы минимизации и тем самым отыскания решения л. а. с.

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

3. Методы решения хорошо обусловленных систем достаточно хорошо развиты и стали «классическими». Задача состоит в том, чтобы из их многообразия отобрать необходимый минимум при создании оптим. матем. обеспечения конкретных машин и систем. Рассмотрим более подробно лишь отдельные Л. а. с. у. с. р., получившие наибольшее распространение при решении л. а. с. на ЦВМ и АВМ. Прямые (точные) методы обычно применяются при небольшом порядке системы. Из таких методов рассмотрим компактную схему метода Гаусса с аналогом выбора главного элемента по столбцу, метод отражений и метод квадратного корня (последний для положительно определенной матрицы). Везде будем предполагать, что суммы парных произведений компонент векторов вычисляются на ЦВМ с округлением лишь результатов, причем ЦВМ работает в режиме с плавающей запятой.

Компактная схема при осуществляет непосредственное разложение матрицы на две треугольные: где L — нижняя треугольная с единицами на главной диагонали, верхняя треугольная. Разложение записывается в виде вспомогательной матрицы

элементы которой вычисляются по ф-лам:

Правая часть преобразуется в вектор по ф-ле

Решение вычисляется как

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

так что после этого

Аналогичные преобразования выполняют и над элементами правой части. Такой выбор главного элемента обеспечивает . Реализация указанного алгоритма на ЦВМ требует хранения чисел, выполнения делений, умножений, сложений и порядка логических операций. При этом здесь и дальше учитываются лишь главные степени

Для характеристики точности любого из прямых методов можно использовать понятие эквивалентного возмущения (э. в.), которое указывает, какое изменение исходных данных системы эквивалентно суммарному влиянию погрешностей округления на вычисляемое решение. Обозначим символами с индексом t Вычисленные величины, где t — число двоичных разрядов мантиссы машинного представления числа. Решение точно удовлетворяет не системе (1), а системе , где соответствующие э. в. Главную часть во всех прямых методах составляют погрешности округления, возникающие при разложении (преобразовании) матрицы А. В случае компактной схемы: , где константа, зависящая от величины

Метод отражений основан на ортогональном преобразовании исходной системы к системе с треугольной матрицей. Преобразования над заданной матрицей выполняются по правилу: с помощью матриц отражения По данному вектору z и единичному координатному вектору всегда можно построить матрицу отражения единичная матрица, W — матрица-столбец), для которой Для этого достаточно положить )].

Ha 1-ом шаге полагаем , где столбец матрицы Тогда а имеет знак где . В результате , где В — матрица 1-го порядка. Далее процесс повторяется для матрицы В. Аналогичные преобразования выполняются и над правой частью: Полученная в итоге система с треугольной матрицей решается простым методом последовательного исключения. Данный алгоритм требует также ячеек памяти ЦВМ, делений, умножений, сложений, логических операций и операций извлечения квадратного корня. Для него

Вычислителъная схема метода квадратного корня (для положительно определенной матрицы) состоит в представлении А в виде где S — верхняя треугольная матрица, и решении двух треугольных систем Элементы матрицы S находят по ф-лам:

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

Итеративные методы решения линейных систем (1) на ЦВМ применяют обычно при больших , а также для уточнения решения при любом Одним из простейших итерационных методов является метод последовательных приближений , где задано. Для сходимости метода при любом необходимо и достаточно, чтобы все собственные значения матрицы В были по модулю меньше 1. Если то погрешность метода

Если В представлено в виде и

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

используя тождество

где не зависят от номера итерации и вычисляются лишь один раз. Ошибка округления метода

где и равно указанным выше или (учтены лишь члены первой степени относительно . п. пр. в канонической форме может быть представлен в виде

где . Если А — симметричная и положительно определенная матрица, то для решения а. с. (1) могут быть применены итеративные методы с ускорением сходимости, реализуемые по схеме

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

При этом итеративный процесс (4) сходится со скоростью геом. прогрессии, знаменатель которой . В отличие от одношаговых (4) двухшаговые итеративные методы в канонической форме записываются в виде

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

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

Решение систем линейных алгебр, ур-ний с вещественными коэфф. можно произвести также на АВМ, пользуясь методом аналогий или квазианалогий. Суть метода аналогий заключается в том, что из элементов АВМ собирается цепь, электр. состояние которой описывается системой ур-ний, подобной системе, подлежащей решению. Метод квазианалогий отличается тем, что собирается цепь, ур-ния которой не подобны, а лишь эквивалентны заданным в том смысле, что среди их решений содержатся решения заданной системы. Метод квазианалогий применяют тогда, когда не существует цепи, ур-ния которой подобны заданным, либо тогда, когда такая цепь существует, но является неустойчивой. Наиболее перспективны квазианалоговые модели систем линейных алгебр, ур-ний. Их можно разбить в соответствии с их свойствами на три группы: 1) модели, пригодные для получения нормального решения совместных систем; 2) модели, пригодные для получения нормального решения совместных и несовместных систем при условии, что число ур-ний больше или равно числу неизвестных, а ранг матрицы равен числу неизвестных: 3) модели, пригодные для решения систем общего вида, но дающие решение, приближенное к нормальному. В моделях последней группы реализуется метод регуляризации Тихонова. В моделях, пригодных для получения нормального решения несовместимых систем, имеются напряжения, пропорциональные невязкам заданных ур-ний. Относительная погрешность решений систем алгебр, ур-ний, получаемых на АВМ, в зависимости от обусловленности обычно колеблется от нескольких десятых процента до нескольких процентов.

Лит.. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М.- Л., 1963 [библиогр. с. 677—734]; Пухов Г. Е., Борковский Б. А. Принципы построения квазианалоговых моделей систем линейных алгебраических уравнений. В кн.: Доклады четвертой межвузовской конференции по применению физического и математического моделирования в различных отраслях техники, сб. 3. М., 1962; Воеводин В. В. Численные методы алгебры. Теория и алгорифмы. М., 1966 [библиогр. с. 247—248]; Фаддеев Д. К., Кублановская В. Н., Фаддеева В. Н. Линейные алгебраические системы с прямоугольными матрицами. В кн.: Материалы Международной летней школы по численным методам, в. 1. М., 1968; Глушков В. М., Молчанов И. Н., Николенко Л. Д. О наборе программ для решения

систем линейных алгебраических уравнений на машинах серии «Мир». «Кибернетика», 1968, № 6; Самарский А. А. Введение в теорию разностных схем. М., 1971 [библиогр. с. 538—550]; Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. Пер. с англ. М., 1969 [библиогр. с. 160—163]; Уилкинсон Дж. X. Алгебраическая проблема собственных значений. Пер. с англ. М., 1970 [библиогр. с. 559—564].

Б. А. Борковский, В. В. Иванов, И. Н. Молчанов, Л. Д. Николепко.