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

Транскрипт

1 6. Вырожденные и плохо обусловленные СЛАУ 1 6. Вырожденные и плохо обусловленные СЛАУ Рассмотрим теперь два типа СЛАУ (27) с квадратной матрицей A размера MxM: вырожденная система (с нулевым определителем A =0); плохо обусловленная система (определитель A не равен нулю, но число обусловленности очень велико). Несмотря на то, что эти типы систем уравнений существенно отличаются друг от друга (для первого решение отсутствует, а для второго существует и единственно), с практической точки зрения вычислителя, между ними много общего. Вырожденная система это система, описываемая матрицей с нулевым определителем A =0 (сингулярной матрицей). Поскольку некоторые уравнения, входящие в такую систему, представляются линейной комбинацией других уравнений, то, фактически, сама система является недоопределенной. Несложно сообразить, что, в зависимости от конкретного вида вектора правой части b, существует либо бесконечное множество решений, либо не существует ни одного. Рассмотрим первый случай, когда СЛАУ A x=b с сингулярной квадратной матрицей A не имеет ни одного решения. Этот вариант сводится к построению нормального псевдорешения (т.е. выбору из бесконечного множества решений такого, которое наиболее близко к определенному, например, нулевому, вектору). Приведем пример такой задачи (для системы двух уравнений) A= , b= (37) СЛАУ (37) проиллюстрирована рис. 19, который показывает, что два уравнения, задающие систему, определяют на плоскости (x 1, x 2) две параллельные прямые. Прямые не пересекаются ни в

2 2 6. Вырожденные и плохо обусловленные СЛАУ одной точке координатной плоскости, и решения системы, соответственно, не существует. Заметим, что СЛАУ, заданная несингулярной квадратной матрицей размера 2x2, определяет на плоскости пару пересекающихся прямых (см. рис ниже). Также стоит сказать, что, если бы система была совместной, то геометрическим изображением уравнений были бы две совпадающие прямые, описывающие бесконечное число решений. Рис. 19. Графическое представление несовместной СЛАУ Рис. 20. График сечений невязки f(x)= A x b в зависимости от x 1 Несложно догадаться, что в рассматриваемом сингулярном случае псевдорешений системы (37), минимизирующих невязку A x b, будет бесконечно много, и лежать они будут на третьей прямой, параллельной двум показанным на рис. 19 и расположенной посередине между ними. Это иллюстрирует рис. 20, на котором представлено несколько сечений функции невязки f(x)= A x b, которые говорят о наличии семейства минимумов одинаковой глубины. Для определения единственного решения следует выбрать из всего множества псевдорешений то, которое обладает

3 6. Вырожденные и плохо обусловленные СЛАУ 3 наименьшей нормой. Таким образом, в сингулярном случае для получения выделенного решения надо численно решить многомерную задачу минимизации. Однако, как мы увидим в дальнейшем, более эффективным способом будет использование регуляризации или ортогональных матричных разложений (см. 7 и 10 соответственно). Обратимся теперь к плохо обусловленным системам, т.е. СЛАУ с матрицей A, у которой определитель не равен нулю, но число обусловленности A -1 A велико. Несмотря на то, что плохо обусловленные системы имеют единственное решение, на практике искать это решение чаще всего не имеет смысла. Рассмотрим свойства плохо обусловленных СЛАУ на двух конкретных примерах очень близких плохо обусловленных СЛАУ с одинаковой правой частью b и мало отличающимися матрицами A и B: A= B=, b=, 3 5. (38) Несмотря на близость этих систем, их точные решения оказываются очень далекими друг от друга, а именно: y A = , y B = (39) Если вспомнить о наличии шума, т.е. о всегда присутствующей погрешности входных данных, то становится ясным, что решать плохо обусловленные системы стандартными методами не имеет вовсе никакого смысла. Напомним, что задачи, для которых малые ошибки модели (матрицы A и вектора b) приводят к большим ошибкам решения, называются некорректными. Таким образом, плохо обусловленные СЛАУ являются типичным примером некорректных задач. Кроме того, следует отметить, что для системы двух уравнений точное решение получить легко, однако при решении СЛАУ большой размерности (в том числе и «точным» алгоритмом

4 4 6. Вырожденные и плохо обусловленные СЛАУ Гаусса) даже незначительные ошибки округления, неминуемо накапливаемые при расчетах, приводят к огромным погрешностям результата. Возникает вопрос: имеет ли смысл искать численное решение, если заранее известно, что, в силу неустойчивости самой задачи, оно может оказаться совершенно неправильным? Чтобы еще лучше понять причину некорректности, полезно сравнить графическую интерпретацию хорошо (рис. 21) и плохо (рис. 22) обусловленной системы двух уравнений. Решение системы визуализируется точкой пересечения двух прямых линий, изображающих каждое из уравнений. Рис. 21. График хорошо обусловленной СЛАУ Рис. 22. График плохо обусловленной СЛАУ Из рис. 22 видно, что прямые, соответствующие плохо обусловленной СЛАУ, располагаются в непосредственной близости друг от друга (почти параллельны). В связи с этим, малые ошибки в расположении каждой из прямых могут привести к значительным погрешностям локализации точки их пересечения (решения СЛАУ) в противоположность случаю хорошо обусловленной системы, когда малые погрешности в наклоне прямых мало повлияют на место точки их пересечения (рис. 21).

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

10. QR- и SVD- разложения: «плохие» СЛАУ 1 10. QR- и SVD- разложения: «плохие» СЛАУ Среди матричных разложений особую роль играют ортогональные, обладающие свойством сохранения нормы вектора. Напомним

7. Регуляризация 1 7. Регуляризация Для решения некорректных задач советским математиком Тихоновым был предложен простой, но чрезвычайно эффективный метод, называемый регуляризацией и основанный на привлечении

Пример: взвешивание 1 Пример: взвешивание Приведем еще более простую интерпретацию обратной задачи, связанной с обработкой результатов какого-либо эксперимента, например, взвешивания предметов двух типов

Тема Численные методы линейной алгебры - - Тема Численные методы линейной алгебры Классификация Выделяют четыре основных раздела линейной алгебры: Решение систем линейных алгебраических уравнений (СЛАУ)

УДК 55 Исабеков КА Маданбекова ЭЭ ЫГУ им КТыныстанова О ПРИБЛИЖЕННОМ РЕШЕНИИ ПЛОХО ОБУСЛОВЛЕННЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ В данной статье приводятся алгоритмы двух методов решения плохо

Специальный вычислительный практикум с н с Андрушевский Николай Матвеевич, факультет ВМК МГУ Аннотация В основу практикума положено подробное изучение метода сингулярного разложения матриц и его применение

Переопределенные системы линейных уравнений Скалько Юрий Иванович Цыбулин Иван Шевченко Александр Переопределенные СЛАУ Переопределенные СЛАУ Рассмотрим СЛАУ Ax = b, но в случае, когда уравнений больше,

Системы линейных алгебраических уравнений Основные понятия Системой линейных алгебраических уравнений (СЛАУ) называется система вида a a a, a a a, a a a Ее можно представить в виде матричного уравнения

Ne Экзамен по ЛА для бакалавров экономики в 04-0 уч году, Найдите вектор Ne (6 4 ; 6 8) и Ne ДЕМОвариант 0 (x ; y)(у которого Ne и x < 0) такой, чтобы система векторов (x ; y) образовывала бы ортогональный

Уравнение прямой в пространстве 1 Прямая как пересечение двух плоскостей. Система двух линейных уравнений с тремя неизвестными. Прямую в пространстве можно задать как пересечение двух плоскостей. Пусть

ЛЕКЦИЯ 6 СПЕКТРАЛЬНЫЕ ЗАДАЧИ. Методы спуска На прошлой лекции были рассмотрены итерационные методы вариационного типа. Для системы Au = f, для которой выполняется A = A, был введен функционал Φ(u, u)

11. Линейная редукция 1 11. Линейная редукция Завершим разговор о линейных обратных задачах представлением еще одного подхода, называемого редукцией. По сути, он очень близок к регуляризации (в некоторых

01 1. Найдите общее и базисное решения системы уравнений: x + x + 3x = 26, 2x 12x x = 22, x + 3x + 2x = 20, выбрав в качестве базисных переменных x и x. Ответ: Если в качестве базисных переменных выбрать

Демонстрационный вариант 01 1. Найдите общее и базисное решения системы уравнений: x + x + 3x = 26, 2x 12x x = 22, x + 3x + 2x = 20, выбрав в качестве базисных переменных x и x. 2. Найдите базис системы

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени НЭ Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» ÀÍ Êàíàòíèêîâ,

УДК 57.9 Игрунова С.В., кандидат социологических наук, доцент доцент кафедры «Информационных систем» Россия, г. Белгород Кичигина А.К. студент 4 курс, институт «Инженерных технологий и естественных наук»

6 Методы приближения функций. Наилучшее приближение. Рассмотренные в прошлой главе методы приближения требуют строгой принадлежности узлов сеточной функции результирующему интерполянту. Если не требовать

ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ ЗАНЯТИЕ МАТРИЦЫ И ДЕЙСТВИЯ НАД НИМИ Дать определение матрицы Классификация матриц по размерам Что такое нулевая и единичная матрицы? При каких условиях матрицы считаются равными?

) Понятие СЛАУ) Правило Крамера решения СЛАУ) Метод Гаусса 4) Ранг матрицы, теорема Кронекера-Капелли 5) Решение СЛАУ обращением матриц, понятие обусловленности матриц) Понятие СЛАУ О. СЛАУ система

Параллельные вычисления в томографии Алгебраические методы вычислительной томографии. Задача вычислительной томографии в дискретной форме Задача вычислительной томографии в дискретной форме. В отличие

ЛЕКЦИЯ 2 ЧИСЛЕННОЕ РЕШЕНИЕ СЛАУ Как правило, при решении большинства практических задач задача решения систем линейных алгебраических уравнений (СЛАУ) встречается в виде некоторой вспомогательной подзадачи.

Образцы базовых задач по ЛА Метод Гаусса Определенные системы линейных уравнений Решите систему линейных уравнений методом Гаусса x 6 y 6 8, 6 x 6 y 6 Решите систему линейных уравнений методом Гаусса 6

Исследование операций Определение Операция - мероприятие, направленное на достижение некоторой цели, допускающее несколько возможностей и их управление Определение Исследование операций совокупность математических

Лекция3. 3. Метод Ньютона (касательных. Зададим некоторое начальное приближение [,b] и линеаризуем функцию f(в окрестности с помощью отрезка ряда Тейлора f(= f(+ f "((-. (5 Вместо уравнения (решим

Уравнения прямой и плоскости Уравнение прямой на плоскости.. Общее уравнение прямой. Признак параллельности и перпендикулярности прямых. В декартовых координатах каждая прямая на плоскости Oxy определяется

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,

Примеры выполнения контрольных работ при заочном обучении Контрольная работа 1 (КР-1) Тема 1. Линейная алгебра Задача 1 Необходимо решить систему уравнений, представленную в задании в виде Постоянные параметры

Московский Государственный Технический Университет им. Н.Э. Баумана Факультет Фундаментальные науки Кафедра Высшая математика Аналитическая геометрия Модуль 1. Матричная алгебра. Векторная алгебра Лекция

Билет. Матрицы, действия над ними.. Уравнение параболы в канонической системе координат. Билет. Свойства матричных операций.. Взаимное расположение прямой и плоскости. Угол между ними, условия параллельности

3 СОДЕРЖАНИЕ 1. Цели и задачи дисциплины 4. Место дисциплины в структуре ОПОП 4 3. Структура и содержание дисциплины 5 3.1. Структура дисциплины 5 3.. Содержание дисциплины 6 4. Перечень учебно-методического

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ Занятие НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ БЕЗУСЛОВНОГО ЭКСТРЕМУМА Постановка задачи Дана дважды непрерывно дифференцируемая функция f (), определенная на множестве X R Требуется исследовать

Решения задач по алгебре за второй семестр Д.В. Горковец, Ф.Г. Кораблев, В.В. Кораблева 1 Линейные векторные пространства Задача 1. Линейно зависимы ли векторы в R 4? a 1 = (4, 5, 2, 6), a 2 = (2, 2, 1,

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Финансовый университет при Правительстве Российской Федерации» (Финансовый университет) КАФЕДРА «МАТЕМАТИКА»

Xətti ər Rus) üui ithhn sullrı Показать, что вектора;;) ;;) ; ;) образуют базис вектора и написать линейную комбинацию вектора Если;;) на эти вектора найти Х из уравнения Показать, что вектора;)

Теорема Кронекера-Капелли. Решение СЛАУ методом Гаусса. Ранг матрицы. Рассмотрим прямоугольную матрицу имеющую m строк и столбцов: A. m m m Выделим в этой матрице произвольные строк и столбцов. Элементы

Системы линейных уравнений с двумя переменными Система уравнений вида называется системой линейных уравнений с двумя переменными. Решением системы уравнений с двумя переменными называется пара значений

ЛИНЕЙНАЯ АЛГЕБРА Лекция Прямая и плоскость в пространстве Содержание: Уравнение плоскости Взаимное расположение плоскостей Векторно-параметрическое уравнение прямой Уравнения прямой по двум точкам Прямая

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики процессов управления А. П. ИВАНОВ, Ю. В. ОЛЕМСКОЙ ПРАКТИКУМ ПО ЧИСЛЕННЫМ МЕТОДАМ МИНИМИЗАЦИЯ КВАДРАТИЧНОЙ ФУНКЦИИ Методические

0 г 6 Труды ФОРА ЧИСЛО ОБУСЛОВЛЕННОСТИ МАТРИЦЫ КАК ПОКАЗАТЕЛЬ УСТОЙЧИВОСТИ ПРИ РЕШЕНИИ ПРИКЛАДНЫХ ЗАДАЧ Р Цей, ММ Шумафов Адыгейский государственный университет, г Майкоп Число обусловленности матрицы

МАТРИЦЫ, ОПРЕДЕЛИТЕЛИ, СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ Метод окаймляющих миноров нахождения ранга матрицы A = m m m минора Минором k порядка k матрицы А называется любой определитель k-го порядка этой матрицы,

ЛЕКЦИЯ 4 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ Для того чтобы уменьшить погрешность, связанную с округлением, прибегают к следующему алгоритму Пусть u точное решение системы, u численное решение Тогда введем

1. Линейные системы и матрицы 1. Дать определение умножения матриц. Коммутативна ли эта операция? Ответ пояснить. Произведение C матриц A и B определяется как m p m p A B ij = A ik B kj. Операция не коммутативна.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Ю.Е. Воскобойников А.А. Мицель НЕКОРРЕКТНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОЙ

ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ В разделе «Численные методы линейной алгебры» рассматриваются численные методы решения систем линейных алгебраических уравнений (СЛАУ) и численные методы решения задач

АНАЛИТИЧЕСКАЯ ГЕОМЕТРИЯ 3 ПОТОК Лектор П. В. Голубцов 1.1. Векторы. Список вопросов к первой части экзамена 1. Сформулируйте определение линейных операций над векторами. Перечислите свойства линейных операций

Системы линейных алгебраических уравнений Рассмотрим систему m линейных алгебраических уравнений с неизвестными b b () m m m bm Система () называется однородной если все её свободные члены b b b m равны

4. Системы линейных уравнений. Основные понятия Уравнение называется линейным если оно содержит неизвестные только в первой степени и не содержит произведений неизвестных т.е. если оно имеет вид + + +

Линейная алгебра Лекция 7 Векторы Введение В математике есть два рода величин скаляры и векторы Скаляр это число, а вектор интуитивно понимается как объект, имеющий величину и направление Векторное исчисление

Список вопросов к экзамену по численным методам (28 мая 2018г.) 0.1 Численное интегрирование 1. Перечислить приёмы вычисления несобственных интегралов. Построить квадратурную формулу для вычисления интеграла

Параллельные вычисления в томографии Метод простой итерации. Метод скорейшего спуска. Метод ART. Метод SIRT. В методе простой итерации релаксационные множители τ k и матрицы H k не зависят от номера

Введение в линейную алгебру Матрицы. Определение. Таблица m n чисел вида m m n n mn состоящая из m строк и n столбцов называется матрицей. Элементы матрицы нумеруются аналогично элементам определителя

ЛЕКЦИЯ 7 ИНТЕРПОЛЯЦИЯ На прошлой лекции была рассмотрена задача решения переопределенной системы. Такая система имеет вид: a 11 x 1 + a 1 x + + a 1 x = f 1, { a 1 x 1 + a x + + a x = f, { a 1 x 1 + a x

ВОПРОСЫ ТЕОРИИ I. МАТРИЦЫ, ОПРЕДЕЛИТЕЛИ 1) Дать определение матрицы. Что такое нулевая и единичная матрицы? При каких условиях матрицы считаются равными? Как выполняется операция транспонирования? Когда

Лекция 7 ПРИВЕДЕНИЕ КРИВОЙ ВТОРОГО ПОРЯДКА К КАНОНИЧЕСКОМУ ВИДУ. Преобразование базисов и координат на плоскости Пусть на плоскости заданы две прямоугольные декартовы системы координат с общим началом:

Линейная алгебра Модуль 1. Линейные и евклидовы пространства. Линейные операторы в линейном пространстве Лекция 1.4 Аннотация Собственные векторы и собственные значения линейного оператора, их свойства.

УДК. СИНТЕЗ РЕКУРСИВНЫХ ЦИФРОВЫХ ФИЛЬТРОВ ПО ИМПУЛЬСНОЙ ХАРАКТЕРИСТИКЕ, ОПРЕДЕЛЯЕМОЙ ЭЛЕМЕНТАРНОЙ МАТЕМАТИЧЕСКОЙ ФУНКЦИЕЙ Никитин Д.А., Ханов В.Х. Введение В современном арсенале методов синтеза рекурсивных

Глава 8 Функции и графики Переменные и зависимости между ними. Две величины и называются прямо пропорциональными, если их отношение постоянно, т. е. если =, где постоянное число, не меняющееся с изменением

Метод Гаусса (метод исключения неизвестных) Две системы называются эквивалентными (равносильными) если их решения совпадают. К эквивалентной системе можно перейти с помощью элементарных преобразований

Искомый вектор

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

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

такую, что

Полагаем, что величины и d известны.

Так как вместо системы (1) имеем систему (2), то можем найти лишь приближенное решение системы (1). Метод построения приближенного решения системы (1) должен быть устойчивым к малым изменениям исходных данных.

Псевдорешением системы (1) называется вектор , минимизирующий невязку на всем пространстве .

Пусть х 1 –некоторый фиксированный вектор из , определяемый обычно постановкой задачи.

Нормальным относительно вектора х 1 решением системы (1) называется псевдорешение х 0 с минимальной нормой , то есть

где F-совокупность всех псевдорешений системы (1).

Причем

где ¾компоненты вектора х.

Для любой системы вида (1) нормальное решение существует и единственно. Задача нахождения нормального решения плохо обусловленной системы (1) является некорректно поставленной.

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

Согласно указанному методу построим сглаживающий функционал вида

и найдем вектор , минимизирующий на этот функционал. Причем параметр регуляризации a однозначно определен из условия

где .

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

Компоненты вектора являются решениями системы линейных алгебраических уравнений, которая получается из условия минимума функционала (4)

и имеет вид

где Е-единичная матрица,

¾эрмитово сопряженная матрица.

На практике для выбора вектора нужны дополнительные соображения. Если их нет, то полагают =0.

Для =0 систему (7) запишем в виде

где

Найденный вектор будет являться приближенным нормальным решением системы (1).

Остановимся на выборе параметра a. Если a=0, то система (7) переходит в плохо обусловленную систему. Если a велико, то система (7) будет хорошо обусловлена, но регуляризованное решение не будет близким к искомому решению системы (1). Поэтому слишком большое или слишком малое a не пригодны.

Обычно на практике проводят расчеты с рядом значений параметра a. Например,

Для каждого значения a находят элемент , минимизирующий функционал (4). В качестве искомого значения параметра регуляризации берется такое число a, для которого с требуемой точностью выполняется равенство (5) или (6).

III. ЗАДАНИЕ

1. Построить систему линейных алгебраических уравнений, состоящую из трех уравнений с тремя неизвестными, с определителем, величина которого имеет порядок 10 -6 .

2. Построить вторую систему, аналогичную первой, но имеющую другие свободные члены, отличающиеся от свободных членов первой системы на величину 0,00006.

3. Решить построенные системы методом регуляризации (полагая =0 и d=10 -4) и каким-либо другим методом (например, методом Гаусса).

4. Сравнить полученные результаты и сделать выводы о применимости использованных методов.

IV. ОФОРМЛЕНИЕ ОТЧЕТА

В отчете должны быть представлены:

1. Название работы.

2. Постановка задачи.

3. Описание алгоритма (метода) решения.

4. Текст программы с описанием.

5. Результаты работы программы.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. - М.: Наука, 1979. 286 с.

2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. - М.: БИНОМ. Лаборатория Знаний, 2007 636с.

Лабораторная работа № 23

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

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

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

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

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

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

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

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

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

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

Лабораторная работа № 3

Решение плохо обусловленных систем линейных алгебраических уравнений

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

Входные параметры: n-целое положительное число, равное порядку n системы; а - массив из n х n действительных чисел, содержащий матрицу коэффициентов системы; b - массив из n действительных чисел, содержащий столбец свободных членов системы (b(1) = b 1 , b(2)=b 2, …b(n)=b n).

Выходные параметры: х – решение системы; p-количество итераций.

Схема алгоритма приведена на рисунке 18.

Текст программы:

procedure regul(N:Integer;a:Tmatr;b:Tvector;var X:Tvector; var p:integer);

var a1,a2:tmatr; b1,b2,x0:tvector; alfa,s1,s:real; max,eps:real; i,j,k,l:integer;

Out_Slau_T(n,a,b);

For I:=1 To n Do {получение А Т А}

For K:=1 To N Do

For J:=1 To N Do S:=S+A*A;

For I:=1 To N Do {получение А Т В}

For J:=1 To N Do

Begin S:=S+A*B[j];

alfa:=0; {нач-ое знач-е альфа}

k:=0; {кол-во итераций}

alfa:=alfa+0.01; inc(k); a2:=a1;

for i:=1 to N do a2:=a1+alfa; {получение А Т А+alfa}

for i:=1 to N do b2[i]:=b1[i]+alfa*x0[i]; {получение А Т В+alfa}

SIMQ(n,a2,b2,l);

a2:=a1; X:=b2; x0:=X; b2:=b1;

vozm(N,eps,a2,b2);

simq(n,a2,b2,l);

for i:=2 to n do

if abs(b2[i]-X[i])>max then max:=abs(b2[i]-X[i]);

X1 = 1.981 X2 = 0.4735

Рисунок 18 - Схема алгоритма метода регуляризации

Варианты заданий для решения плохо обусловленных систем методом регуляризации приведены в таблице 3.

Метод вращения (Гивенса)

Схема алгоритма приведена на рисунке 19.

Пример. Решить систему уравнений

Текст программы:

PROCEDURE Vrash;

Var I,J,K: Integer; M,L,R: Real; F1:TEXT; Label M1,M2;

Out_Slau_T(nn,aa,b);

for i:=1 to Nn do

For I:=1 To Nn-1 Do Begin

For K:=I+1 To Nn Do Begin

If (Aa0.0) Then Goto M1;If (Aa0.0) Then Goto M1;

1:M:=Sqrt(Aa*Aa+Aa*Aa);

L:=-1.0*Aa/M;

M2:For J:=1 To Nn Do Begin

R:=M*Aa-L*Aa;

Aa:=L*Aa+M*Aa;

R:=M*Aa-L*Aa;

Aa:=L*Aa+M*Aa;

For I:=Nn Downto 1 Do Begin

For K:=0 To Nn-I-1 Do Begin M:=M+Aa*Aa; End;

Aa:=(Aa-M)/Aa; End;

for i:=1 to Nn do x[i]:=Aa;End;

Вычисления по программе привели к следующим результатам:

X1 = 1.981 X2 = 0.4735

Рисунок 19 - Схема алгоритма метода Гивенса (вращения)

Варианты заданий

Таблица 3

	Матрица A				Матрица A

Тема лабораторной работы №3 для контроля знаний проиллюстрирована контрольно – обучающей программой.

Лабораторная работа № 4

Решение нелинейных уравнений и систем нелинейных уравнений

Метод простых итераций

Порядок выполнения лабораторной работы:

Найти нулевое приближение решения;

Преобразовать систему f(x) = 0 к виду х = Ф(х);

Проверить условие сходимости метода.

Схема алгоритма приведена на рисунке 20.

Пример. Решить методом простых итераций систему

В качестве нулевого приближения выберем точку х=1, у = 2.2, z = 2. Преобразуем систему к виду

Текст программы:

PROCEDURE Iteraz;

Var I,J,K,J1: Integer;

X2,X3,Eps: Real;

Eps:=0.01; X2:=0.0; K:=1;

For J:=1 To Nn Do Begin

For I:=1 To Nn Do Begin S:=S+Aa*Xx[i]; End;

For J1:=1 To Nn Do Begin Xx:=R; End; X3:=Xx;

For I:=1 To Nn Do Begin If (Xx[i]>=X3) Then X3:=Xx[i]; Еnd;

For I:=1 To Nn Do Begin Xx[i]:=Xx[i]/X3; End;

X1:=X3; U:=Abs(X2-X1); U1:=U/Abs(X1);

If (U1>=Eps) Then X2:=X1;

Until ((K>=50)or(U1

Вычисления по программе привели к следующим результатам:

X(1)= 1.1132 Х(2)= 2.3718 Х(3)= 2.1365

Количество итераций:5

Рисунок 20 - Схема алгоритма метода простых итераций

Метод Ньютона

Программу можно использовать для решения систем не выше десятого порядка.

Входные параметры: n - число уравнений системы (совпадает с числом неизвестных), n£10; х-массив из n действительных чисел, содержащий начальное приближение решения; f- имя внешней процедуры f(n, х, у), вычисляющей по заданным значениям х, расположенным в элементах массива х, текущие значения функции f и размещающей их в элементах массива у; g - имя внешней процедуры g(n, x, d), вычисляющей по заданным значениям х из массива х элементы матрицы
,которая размещается в массиве d размерности n x n; eps - значение условия окончания итерационного процесса.

Выходные параметры: х - массив из n действительных чисел (он же входной) содержит при выходе из подпрограммы приближенное значение решения; k-количество итераций.

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)