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

Обусловленность систем линейных уравнений

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

Числом обусловленности линейного оператора A, действующего в нормированном пространстве а также числом обусловленности системы линейных уравнений Ax = у назовем величину

Таким образом, появляется связь числа обусловленности с выбором нормы.

Предположим, что матрица и правая часть системы заданы неточно. При этом погрешность матрицы составляет dA, а правой части — dу. Можно показать, что для погрешности dx имеет место следующая оценка ( ):

В частности, если dA = 0, то

При этом решение уравнения Ax = у не при всех у одинаково чувствительно к возмущению dу правой части.

Свойства числа обусловленности линейного оператора:

1.

причем максимум и минимум берутся для всех таких x, что Как следствие,

2.

3

где и — соответственно минимальное и максимальное по модулю собственные значения матрицы A. Равенство достигается для самосопряженных матриц в случае использования евклидовой нормы в пространстве

4.

Матрицы с большим числом обусловленности (ориентировочно ) называются плохо обусловленными матрицами. При численном решении систем с плохо обусловленными матрицами возможно сильное накопление погрешностей, что следует из оценки для погрешности dx. Исследуем вопрос о погрешности решения, вызванной ошибками округления в ЭВМ при вычислении правой части. Пусть t — двоичная разрядность чисел в ЭВМ. Каждая компонента вектора правой части округляется с относительной погрешностью Следовательно,

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

Итак – принципиально остаются две проблемы –

1.не обеспечивается обоснованная сходимость алгоритма к единственной (в случае модельного примера- истинной) структуре и

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

Для АШР даже в случае применения для МНК оценки процедуры Грамма-Шмидта не разрешается вопрос о единственности модели – просто оценки параметров становятся наиболее точными и несмещенными

Т.о. гарантированное нахождение всего множества подходящих решений в реальных задачах (при — количество линейных входных аргументов и степени ПП p >3) получим только после полного

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

Можно еще добавить камень в огород АШР о неиспользуемой возможности вариации уровнем значимости для учета уровня шума в данных

Именно эту проблему предлагает решать МГУА с помощью введения понятия внешних критериев.

Необходимое примечание.

при все типы АШР МВИ, МГУА, другие целесообразные подходы, дают практически одинаково эффективные (или неэффективные) решения. Кривые критериев одинаково асимптотически стремятся к некоторому ненулевому уровню, при подходе к которому и определяется единственная модель.

Каждый из них это делает по своему, и определить адекватность метода по сходимости к нужной модели можно только построив соответствующий вашей задаче модельный пример.

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

И наиболее эффективный подход к решению структурно-параметрического синтеза при данных условиях демонстрирует МГУА

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

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

Основная проблема– проблема необоснованности выбора структуры модели классическими АШГ многократно обостряется в связи с тем что порог используемый критерием Фишера в виде уровня значимости

на самом деле регулирует не только риск ошибки

– его выбор должен учитывать уровень шума и точки его приложения.

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

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

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

Реферат: Численные методы решения систем линейных алгебраических уравнений

Введение

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

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

Любой численный метод линейной алгебры можно рассматривать как некоторую последовательность выполнения арифметических операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым . В противоположном случае численный метод называется итерационным . Прямые методы — это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод переменных направлений, метод релаксации и др.

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

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLABи т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.

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

Учитывая важность выше указанных проблем, тему своей работы мы определили так: «Численные методы решения систем линейных алгебраических уравнений ».

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

Предметом исследования, является выявление эффективности и сравнительная характеристика методов.

· изучить и проанализировать литературу по проблемам численных методов;

· изучить научную и учебную литературу по теме «Численные методы решения систем линейных алгебраических уравнений;

· определить основные этапы изучения темы «Численные методы решения систем линейных алгебраических уравнений»;

· продемонстрировать на примерах использование методов.

Дипломная работа состоит из введения, двух глав, заключения, списка используемой литературы (20 наименований).

Во введении обоснована актуальность темы исследования, определены объект, предмет, проблема и задачи исследования.

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

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

В заключении подведены итоги и сделаны основные выводы.

Глава I. Теоретические основы исследования

§1 ЧИСЛЕННЫЕ МЕТОДЫ

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

Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nхn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.

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

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.

Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:

1. Δ = 0 и каждый из дополнительных определителей Δx_i = 0. Это имеет место только тогда, когда коэффициенты при неизвестных x_i пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.

2. Δ = 0 и хотя бы один дополнительный определитель Δx_i ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных x_i , пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений [7].

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

Пусть дана система линейных уравнений:

Рассмотрим матрицу, составленную из коэффициентов при неизвестных:

Свободные члены и неизвестные можно записать в виде матрицы столбцов:

Тогда, используя правило умножение матриц, эту систему уравнений можно записать так:

Равенство (1) называется матричным уравнением или системой уравнений в матричном виде.

Матрица А коэффициентов при неизвестных называется главной матрицей системы.

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

Любую линейную систему уравнений можно записать в матричном виде. Например, пусть дана система:

Эта система из двух уравнений с тремя неизвестными – x, y,. В высшей математике можно рассматривать системы из очень большого числа уравнений с большим количеством неизвестных и поэтому неизвестные принято обозначать только буквой х, но с индексами:

Запишем эту систему в матричном виде:

Здесь главная матрица системы:

Расширенная матрица будет иметь вид:

Microsoft Office Excel . Если же говорить о программе Excel, которая является одной из наиболее известных в обработке электронных таблиц, то без преувеличения можно утверждать, что ее возможности практически неисчерпаемы.Обработка текста, управление базами данных — программа настолько мощна, что во многих случаях превосходит специализированные программы — редакторы или программы баз данных. Такое многообразие функций может поначалу запутать, нежели заставить применять их на практике. Но по мере приобретения опыта начинаешь по достоинству ценить то, что границ возможностей Excel тяжело достичь.За всю историю табличных расчетов с применением персональных компьютеров требования пользователей к подобным программам существенно изменились. В начале основной акцент в такой программе, как, например, Visi Calc , ставился на счетные функции. Сегодня, положение другое. Наряду с инженерными и бухгалтерскими расчетами организация и графическое изображение данных приобретают все возрастающее значение. Кроме того, многообразие функций, предлагаемое такой расчетной и графической программой, не должно осложнять работу пользователя. Программы для Windows создают для этого идеальные предпосылки.В последнее время многие как раз перешли на использование Windows в качестве своей пользовательской среды. Как следствие, многие фирмы, создающие программное обеспечение, начали предлагать большое количество программ для Windows.

Программа MathCAD по своему назначению позволяет моделировать в электронном документе научно–технические, а также экономические расчёты в форме, достаточно близкой к общепринятым ручным расчётам. Это упрощает составление программы расчёта, автоматизирует перерасчёт и построение графических иллюстраций подобно электронным таблицам Excel, документирование результатов как в текстовом редакторе Word.

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

Достоинством MathCAD является также наличие в его составе электронных книг. Одна из них – учебник по самой программе, другие – справочник по различным разделам математики, физики, радиоэлектроники и др.

К численным методам решения систем линейных уравнений относят такие как: метод Гаусса, метод Крамера, итерационные методы. В методе Гаусса, например, работают над расширенной матрицей системы. А в методе Крамера – с определителями системы, образованными по специальному правилу.

1.2 Метод Гаусса – прямой и обратный ход

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

Будем считать, что a₁₁ ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:

Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а₁₁ .

В результате получим матрицу:

Т. е. первая строка осталась без изменений, а в столбце под а₁ 1 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – a_ij , где I = j.

Повторим наши элементарные преобразования, но уже для элемента α₂₂ .

Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α₂₂ .

Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее — треугольному виду. Т. е. под главной диагональю не окажутся все нули:

Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

Отсюда легко можно найти значение первого корня – x_n = δ_m /γ_mn .

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение x_n-1 -ого корня.

Таким образом, поднимаясь до самого верха обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений [5].

Рассмотрим систему уравнений:

Главный определитель данной системы:

Т. е. система определена и разрешима. Решим ее по методу Гаусса.

Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:

Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C₂ -(a₂₁ /a₁₁ )*C₁ = C₂ -(2/1)*C₁ = C₂ -2*C₁ :

Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C₃ -(a₃₁ /a₁₁ )*C₁ = C₃ -(-1/1)*C₁ = C₃ +C₁ :

Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C₃ -(a₃₂ /a₂₂ )*C₂ = C₃ -(1/-2)*C₂ = C₃ +1/2C₂ :

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

Эта матрица эквивалентна системе:

Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х₃ :

Корень x₃ = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x₂ -3x₃ = 1):

Корень x₂ = 2/5 найден. Подставим его и корень х₃ в верхнее (первое) уравнение системы (x₁ -x₂ +x₃ = 0):

Вывод: Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхнее — треугольной матрицей. Эти действия называют прямым ходом.

2. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).

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

1.3 Итерация для линейных систем

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

Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде:

Разрешим первое уравнение системы относительно х₁ :

Затем разрешим второе уравнение относительно х₂ и т. д. Тогда систему можно переписать в виде:

гдеα = -a_ik /a_ii , i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида:

При этом линейная функция L₁ фактически не зависит от х₁ .

Зададим какие-либо начальные значения неизвестных (нулевые приближения):

Подставляя эти значения в правые части системы (*), получим первые приближения:

Полученные первые приближения могут быть так же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:

Условия сходимости итерационного процесса.

Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х₁ , х₂ , х₃ , х₄ .

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

Это условие можно сформулировать и более точно [20]:

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

1.4 Итерация Якоби

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

Уравнения можно записать в виде:

Это позволяет предложить следующий итерационный процесс:

или (другой вид записи)

Покажем, что если начать с точки P₀ = (х₁ (0) , х₂ (0) , х₃ (0) , х₄ (0) ) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х₁ = 1, х₂ = 2, х₂ = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P₁ = (х₁ (1) , х₂ (1) , х3 (1) , х₄ (1) ) = (1.75, 3.375, 3), ближе, чем P₀ .

Итерация, использующая (3), генерирует последовательность точекk >, которая сходится к решению (2, 4, 3):

Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем [19].

1.5 Итерация Гаусса-Зейделя

Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

Отметим, что итеративный процесс Якоби производит три последовательности – <х₁ (k) >, <х₂ (k) >, <х₃ (k) >, <х₄ (k) >. Кажется разумным, что х₁ (k+1) может быть использовано вместо х₂ (k ). Аналогично х₁ (k+1) и х₂ (k+1) можно использовать в вычислении х₃ (k+1) . Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):

Такой итерационный процесс даст результаты:

Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби [19].

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

Эти формулы как раз и задают собственно итерационный процесс.

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

Это условие можно сформулировать и более точно:

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

3. Следует так же сказать, что итерационный процесс может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.

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

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

Существуют два типа ме­тодов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем об­щего вида и варианты — метод прогонки и методы мат­ричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от по­рядка системы n структуры матрицы.

При изучении итерационных методов мы трактуем си­стему уравнений как операторное уравнение первого ро­да Au = f и излагаем общую теорию итерационных ме­тодов для операторных уравнений при минимальных предположениях относительно оператора А. Общая тео­рия позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γ_i > О и γ₂ >= γ₁ спектра оператора А в некотором энергетиче­ском пространстве H_D ; 2) для случая, когда границы γ₁ и γ₂ неизвестны. Весьма эффективным является попере­менно-треугольный метод.

Основная задача линейной ал­гебры — решение системы уравнений

Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только триви­альное решение, и система (1) имеет единственноерешение

В курсе линейной алгебры решение системы (1) обыч­но выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа дей­ствий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определи­теля требует примерно такого же времени, что и реше­ние системы линейных уравнений современными числен­ными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к боль­шим ошибкам округлений.

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

Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:

1) найти решение одной конкретной задачи (1);

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

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

При теоретических оценках каче­ства алгоритмов их сравнение проводится по числу q ( e ) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].

Метод Гаусса. Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последо­вательного исключения. Процесс решения системы ли­нейных алгебраических уравнений Ax = f (1) по методу Гаусса состоит из двух этапов.

Первый этап (прямой ход). Система (1) приво­дится к треугольному виду

Метод квадратного корня. Этот метод пригоден для систем

с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение

где S — верхняя треугольная, D — диагональная матрица. Решение уравнения Аu=fсводится к последователь­ному решению двух систем

Метод квадратного корня требует порядка N 2 /3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.

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

Перейдем к общему описанию метода итераций для системы линейных алгебраических уравнений

Для ее решения выбирается некоторое начальное приближение у₀ H и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации y_{h +1} выражается через известные предыдущие итерации y_k , y_{k -1} ,… Если при вычислении y_{h +1} используется толь­ко одна предыдущая итерация y_h , то итерационный метод называют одношаговым (или двухслойным) методом; если же y_{k +1} выражается через две итерации y_k и y_{k -1} , то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H -> H — линейный оператор в конеч­номерном пространстве H со скалярным произведе­нием (•, •).

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

(7), где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В -1 , k — номер итерации, τ₁ τ₂ , . τ_{k +1} , . — итерационные параметры, τ_{k +1} > 0. Оператор В может, вообще говоря, зависеть от номера k — для Для простоты изложения мы пред­полагаем всюду, что В не зависит от k .

Если В = Е — единичный оператор, то метод(8) называют явным: y_{h +1} находится по явной формуле

В общем случае, при В≠ Е, метод (7) называют не­явным итерационным методом: для определения y_{h +1} надо решить уравнение:

(9)

Естественно требовать, чтобы объем вычислений для ре­шения .системы By_{k +1} = F_k был меньше, чем объем вы­числений для прямого решения системы Au=f

Точность итерационного метода (7) характеризуется величиной погрешности z_h = у_к — и, т. е. разностью между решением уравнения (7) и точным решением и исход­ной системы линейных алгебраических уравнений. Под­становка y_k = z_k + u в (2) приводит к однородному урав­нению для погрешности:

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

2.1 Общие сведения

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

2.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А — матрица. (1)

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

x_k → x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

, или .

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:

В результате получим систему:

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

Итерационный процесс продолжается до тех пор, пока значения х₁ ( k ), х₂ ( k ), х₃ ( k ) не станут близкими с заданной погрешностью к значениям х₁ ( k -1), х₂ ( k -1), х₃ ( k -1).

2.2.2 Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

,

,

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].

2.3 Метод Зейделя

2.3.1 Описание метода

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

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

Если данное условие выполнено, необходимо проследить, чтобы система была приведена к виду, удовлетворяющему решению методом простой итерации и выполнялось необходимое условие сходимости метода итераций:

, либо

2.3.2 Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью .

Эту систему можно записать в виде:

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

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить [9].

2.4 Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:

6.1. Решение систем линейных алгебраических уравнений. Обусловленность матрицы

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

Определение. Говорят, что задача поставлена корректно, если ее решение существует, единственно и непрерывно зависит от входных данных.

Где А — квадратная, неособенная матрица размерности N, и, следовательно, det(A) ≠ 0, тогда существует единственное решение системы. Чтобы убедиться в корректности задачи (6.1) необходимо еще установить непрерывную зависимость решения от входных данных. Входными данными являются правая часть F и элементы матрицы А.

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

Будем считать, что решение и правая часть задачи (6.1) принадлежат линейному пространству H, состоящему из N-мерных векторов. Введем в H норму, для которой выполнено:

||X||>0, для всех Х≠0H ,

||α X||=| α| ||X||, для любого числа А и ХH ,

||X+Y||≤||X||+||Y||, для любых X и YH .

Определение. Нормой матрицы А, подчиненной данной норме векторов, называется число , для всех Х≠0H .

Наряду с системой (6.1) рассмотрим «возмущенную» систему A Xε = Fδ , которая отличается от (6.1) правой частью. Насколько сильно может измениться решение Х В результате изменения правой части?

Определение. Говорят, что система (6.1) устойчива по правой части, если при любых F и Fδ Справедлива оценка || δx||≤ M || δf ||, где M — постоянная, M >0.

Эта оценка выражает факт непрерывной зависимости решения от правой части, то есть показывает, что || δx|| Стремится к нулю при || δf ||Стремящемся к нулю. Наличие устойчивости очень важно при численном решении систем уравнений, так как никогда нельзя задать правую часть F точно. Погрешность δf возникает в результате округления.

Получим оценку для относительной погрешности решения . Используем неравенство ||F|| ≤ ||A|| ||X|| . Перемножим его с неравенством ||δx||≤ ||A-1|| || δf ||, получим требуемую оценку

.

Определение. Число ρ(A)= называется числом обусловленности матрицы A и характеризует степень зависимости относительной погрешности решения от относительной погрешности правой части. В случае самосопряженной матрицы A =A* это число равно

ρ(A)=,

Где λMax , λmin – максимальное и минимальное по модулю собственные значения матрицы A.

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

Например, для матрицы

Число обусловленности ρ(A)=, И если взять за правую часть системы вектор F= (1,0000, 1,0000)T, то получим решение X=(0,3333, 0,0000)T. Решение «возмущенной» системы с правой частью Fδ = (0,9998, 1,0000)T равно Xε=(5,0000, 2,0000)T.

Если взять матрицу

И за правую часть системы вектор F= (1,0000, 0)T, то получим решение . Решение «возмущенной» системы при изменении коэффициента a22 = 0,421 на 0,433 равно Xε = (47,983, -86,879)T.