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

Транскрипт

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 Функции и графики Переменные и зависимости между ними. Две величины и называются прямо пропорциональными, если их отношение постоянно, т. е. если =, где постоянное число, не меняющееся с изменением

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

Выходные данные сборника:

РЕШЕНИЕ ПЛОХО ОБУСЛОВЛЕННЫХ РАЗРЕЖЕННЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ С ПОМОЩЬЮ КРЫЛОВСКОГО ПОДПРОСТРАНСТВА

Гусева Юлия Сергеевна

студент Самарского государственного аэрокосмического университета имени С.П. Королева,

г. Самара

Е-mail:

Гоголева Софья Юрьевна

доцент Самарского государственного аэрокосмического университета имени С.П. Королева,

г. Самара

Е-mail:

Введение

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

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

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

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

Где: - плохо обусловленная разреженная матрица,

.

В данной работе проводится сравнительный анализ итерацион­ных методов для решения плохо обусловленных разреженных СЛАУ. В качестве исследуемых методов выбраны: метод сопряженных градиентов (CG) , метод минимальных невязок (MinRes), сдвоенный метод сопряженных направлений (CGS), квазиминимальных невязок (QMR) .

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

Таким образом, критерием сравнения итерационных методов решения СЛАУ будут: погрешность результатов, скорость сходимости, структура матрицы.

Результаты численных исследований показали, что для решения СЛАУ с матрицей A являющейся симметричной/несимметричной и хорошо обусловленной к нормальным уравнениям лучше применять метод CG. Если матрица А- симметричная и плохо обусловленная, то лучшую сходимость показал метод MinRes. Для А- несимметрич­ной, плохо обусловленной - метод квазиминимальных невязок .

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

В данной работе было рассмотрено несколько видов предобус­лавливания для метода квазиминимальных невязок с разреженными плохо обусловленными матрицами: левое и правое предобус­лавливание с использованием QR - разложения, левое и правое предобуславливание с использованием LU - разложения, а также с использованием модификации LU - разложения .

Таблица 1.

Сравнение относительной погрешности предобуславливателей

Заключение

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

Список литературы:

1.Голуб Дж., Ван Лоун Ч. Матричные вычисления/ Под ред. В.В. Воеводина. - М.: «Мир», 1999. - 548 с.

2.Деммель Дж. Вычислительная линейная алгебра. Теория и приложения / Пер. с англ.Х.Д. Икрамова. - М.: «Мир», 2001. - 430 c.

3.Писсанецки С. Технология разреженных матриц/ Под ред. Х.Д. Икрамова - М.: «Мир», 1988. - 410 с.

4.Станкевич, И.В. Хранение и использование разреженных матриц в конечно- элементной технологии. Журнал «Наука и Образование». - 2005. - 10 октября.

5.Тьюарсон Р. Разреженные матрицы/ Под ред. Х.Д. Икрамова. - М.: «Мир», 1977. - 172 с.

6.Bucker Martin, Basermann Achim. A comparison of QMR, CGS and TFQMR on a distributed memory machine / Bucker Martin //Mathematics of computation. - 1994 - 31 may

7.Harwell-Boeing Collection - [Электронный ресурс] – Режим доступа. - URL: http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/ (дата обращения: 15.12.2012)

8.Roland W. Freund, Noel M. Nachtigal. QMR: a Quasi-Minimal Residual Method for Non-Hermitian Linear Systems / Roland W. Freund, Noel M. Nachtigal // Journal Math. - 1991. - №60. - p. 315-339.

9.Saad, Y. Iterative methods for sparse linear systems / Y. Saad. // SIAM. - 2003. - 447 p.

Лабораторная работа № 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

Тема лабораторной работы №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-количество итераций.

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

Если , то система (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