Математические задачи в пакете MathCAD 12
         

Глава 8.2.3. Вырожденные и плохо обусловленные системы



Вернемся вновь к СЛАУ Aх=b с квадратной матрицей А размера MхN, которая, в отличие от рассмотренного выше "хорошего" случая (см. разд. 8. Г), требует специального подхода. Обратим внимание на два похожих типа СЛАУ:

  •  вырожденная система (с нулевым определителем |А|=0);
  •  плохо обусловленная система (определитель А не равен нулю, но число обусловленности очень велико).


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




Вырожденные СЛАУ

Вырожденная система — это система, описываемая матрицей с нулевым определителем |A|=0 (сингулярной матрицей). Поскольку некоторые уравнения, входящие в такую систему, представляются линейной комбинацией других уравнений, то фактически сама система является недоопределенной. Несложно сообразить, что, в зависимости от конкретного вида вектора правой части ь, существует либо бесконечное множество решений, либо не существует ни одного. Первый из вариантов сводится к построению нормального псевдорешения (т. е. выбора из бесконечного множества решений такого, которое наиболее близко к определенному, например, нулевому, вектору). Данный случай был подробно рассмотрен в разд. 8.2.2 (см. листинги 8.11—8.13).



Рис. 8.7. Графическое представление несовместной системы двух уравнений с сингулярной матрицей


Рассмотрим второй случай, когда СЛАУ Aх=b с сингулярной квадратной матрицей А не имеет ни одного решения. Пример такой задачи (для системы двух уравнений) проиллюстрирован рис. 8.7, в верхней части которого вводятся матрица А и вектор b, а также предпринимается (неудачная, поскольку матрица А сингулярная) попытка решить систему при помощи функции isolve. График, занимающий основную часть рисунка, показывает, что два уравнения, задающие систему, определяют на плоскости (x0,xi) две параллельные прямые. Прямые не пересекаются ни в одной точке координатной плоскости, и решения системы, соответственно, не существует.

ПРИМЕЧАНИЕ

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




Рис. 8.8. График сечений функции невязки f (х) = |Ах-b|


Несложно догадаться, что в рассматриваемом сингулярном случае псевдорешений системы, минимизирующих невязку |Ax-b|, будет бесконечно много, и лежать они будут на третьей прямой, параллельной двум показанным на рис. 8.7 и расположенной в середине между ними. Это иллюстрирует рис. 8.8, на котором представлено несколько сечений функции f(x)= = | Аx-b |, которые говорят о наличии семейства минимумов одинаковой глубины. Если попытаться использовать для их отыскания встроенную функцию Minimize, ее численный метод будет всегда отыскивать какую-либо одну точку упомянутой прямой (в зависимости от начальных условий). Поэтому для определения единственного решения следует выбрать из всего множества псевдорешений то, которое обладает наименьшей нормой. Можно пытаться оформить данную многомерную задачу минимизации в Mathcad при помощи комбинаций встроенных функций Minimize, однако более эффективным способом будет использование регуляризации (см. ниже) или ортогональных матричных разложений (см. разд. 8.3).

Плохо обусловленные системы

Плохо обусловленная система — это система, у которой определитель А не равен нулю, но число обусловленности |А-1| |А| очень велико. Несмотря на то, что плохо обусловленные системы имеют единственное решение, на практике искать это решение чаще всего не имеет смысла. Рассмотрим свойства плохо обусловленных СЛАУ на двух конкретных примерах (листинг 8.14).

Листинг 8.14. Решение двух близких плохо обусловленных СЛАУ

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

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

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



Рис. 8.9. График хорошо обусловленной системы двух уравнений



Рис. 8.10. График плохо обусловленной системы двух уравнений


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

ПРИМЕЧАНИЕ

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



Метод регуляризации

Для решения некорректных задач, в частности, вырожденных и плохо обусловленных СЛАУ, разработан очень эффективный прием, называемый регуляризацией. В его основе лежит учет дополнительной априорной информации о структуре решения (векторе априорной оценки хо), которая очень часто присутствует в практических случаях. В связи с тем, что регуляризация была подробно рассмотрена в разд. 6.3.3, напомним лишь, что задачу решения СЛАУ Аx=b можно заменить задачей отыскания минимума функционала Тихонова:

Ω(х,λ) = |Ах-b|2+λ|х-х0|2. (8.3)

Здесь Я, — малый положительный параметр регуляризации, который необходимо подобрать некоторым оптимальным способом. Можно показать, что задачу минимизации функционала Тихонова можно, в свою очередь, свести к решению другой СЛАУ:

(АTА+λI)-х=АTВ+λх0, (8.4)

которая при λ->0 переходит в исходную плохо обусловленную систему, а при больших x, будучи хорошо обусловленной, имеет решение х0. Очевидно, оптимальным будет некоторое промежуточное значение А, устанавливающее определенный компромисс между приемлемой обусловленностью и близостью к исходной задаче. Отметим, что регуляризационный подход сводит некорректную задачу к условно-корректной (по Тихонову) задаче отыскания решения системы (8.4), которое, в силу линейности задачи, является единственным и устойчивым.

Приведем, без излишних комментариев, регуляризованное решение вырожденной системы, которая была представлена на рис. 8.8. Листинг 8.15 демонстрирует отыскание решения задачи (8.4), а полученная зависимость невязки и самого решения от параметра регуляризации Я показана на рис. 8.11 и 8.12 соответственно. Важно подчеркнуть, что решения исходной системы и, следовательно, системы (8.4) при λ=0 не существует.

Листинг 8.15.Регуляризация вырожденной СЛАУ

Заключительным шагом регуляризации является выбор оптимального λ. Имеется, по крайней мере, два соображения, исходя из которых, можно выбрать параметр регуляризации, если опираться на зависимость от него невязки. В рассматриваемом примере применим критерий определения λ, опирающийся -на подбор нормы невязки, равной априорной оценке погрешностей задания входных данных: матрицы А и вектора b, т. е. величине |δA| + |5λ|. Например, можно выбрать норму невязки и, соответственно, параметр λ и решение х(λ), которые отмечены на рис. 8.11 и 8.12 пунктирами.

ПРИМЕЧАНИЕ 1

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



ПРИМЕЧАНИЕ 2

Полезно убедиться в том, что формула (8.4) в случае линейной задачи дает тот же результат, что и общая формула (8.3). Для этого достаточно изменить в листинге 8.15 последнюю строку, выражающую решение СЛАУ (8.4), на код, реализующий минимизацию численным методом, как это показано в листинге 8.16. Расчеты (которые требуют значительно большего компьютерного времени) дают тот же самый результат, что был приведен на рис. 8.11 и 8.12.



ПРИМЕЧАНИЕ 3

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




Рис. 8.11. Зависимость невязки регупяризованного решения вырожденной СЛАУ от параметра А. (продолжение листинга 8.15)


ПРИМЕЧАНИЕ 4

Любопытно также применить вместо формулы (8.3) в качестве функционала Тихонова другую зависимость: Ω(х,λ) = |Ах-b|+λ|х-х0 |. Соответствующий пример расчетов вы найдете на компакт-диске.




Рис. 8.12. Регуляризованное решение в зависимости от λ (продолжение листинга 8.15)

Листинг 8.16. Регуляризация СЛАУ при помощи алгоритма минимизации (продолжение листинга 8.15)


Содержание раздела