Особенности и преимущества итерационных методов решения систем линейных алгебраических уравнений
План
Лекция 14. Особенности и условия применимости итерационных методов решения систем линейных алгебраических уравнений
Численные методы решения СЛАУ
, (1)
где 
— 
матрица системы, 
— векторы длины 
неизвестных и правой части соответственно, как уже отмечалось в лекци 5, делятся на два больших класса: прямые (эти методы в предположении отсутствия округлений дают точное решение СЛАУ после конечного, определяемого заранее числа арифметических операций) и итерационные (точное решение в общем случае получается за бесконечное число шагов).
В приложениях часто встречаются системы, элементы матриц которых вычисляются по простым формулам или алгоритмам, а потому для решения систем такого рода желательно было бы иметь такие методы, в которых элементы матриц вообще можно было бы не хранить, а генерировать их по мере необходимости. Очевидно, что рассмотренные ранее прямые методы, в частности, различные варианты метода Гаусса, не обладают таким свойством, т.к. в процессе решения элементы матрицы изменяются. Кроме того, в приложениях часто встречаются задачи, в которых матрица СЛАУ имеет слишком большой размер, что для ее хранения не хватает не только оперативной памяти, но и памяти на внешних носителях. Объем вычислений при решении таких систем прямыми методами занимает очень много времени. В этом случае желательно пользоваться такими методами, которые не меняют элементов матрицы. При этом в оперативной памяти хотелось бы хранить лишь несколько строк (или столбцов) матрицы СЛАУ. Всем перечисленным выше пожеланиям удовлетворяют итерационные методы решения СЛАУ.
Как уже отмечалось, общая идея итерационных методов заключается в следующем: по заданной матрице системы , вектору правой части 
и некоторому начальному приближению 
к решению СЛАУ находится следующее приближение 
, по которому на следующем шаге строится приближение 
к решению и т.д. Получаем бесконечную векторную последовательность 
приближений к решению: , . 
. Итерационный процесс строится таким образом, чтобы 
, где 
— точное решение СЛАУ.
Основные особенности итерационных методов:
1. На каждой итерации элементы матрицы СЛАУ не меняются;
2. Объем вычислений для получения каждого последующего приближения сравним с объемом при умножении матрицы на некоторый вектор. Чаще всего вычисление на каждой итерации и сводится к умножению матрицы на вектор;
3. Если известна структура матрицы или известны формулы для вычисления элементов матрицы, то при реализаци вычислений на ЭВМ всю матрицу не обязательно хранить в памяти;
4. Для систем среднего и малого размера, как правило, более предпочтительными являютсяпрямые методы. Итерационные методы применяются, главным образом, для решения задач большого размера.
Особое преимущество итерационных методов перед прямыми ощущается при решении сильно разреженных систем.
Метод простой итерации плюсы и минусы. Метод простых итераций в общем виде
Пусть дана система n алгебраических уравнений с n неизвестными:
Алгоритм метода простой итерации:
Затем формируется циклический математический процесс, каждый цикл которого представляет собой одну итерацию. В результате каждой итерации получается новое значение вектора неизвестных. Для организации итерационного процесса запишем систему (1) в приведенном виде. При этом слагаемые, стоящие на главной диагонали, нормируются и остаются слева от знака равенства, а остальные переносятся в правую часть. Приведенная система уравнений имеет вид:
Заметим, что никогда не будет достигнуто, однако с каждой последующей итерацией вектор неизвестных все ближе приближается к точному решению.
12. Основная итерационная формула, применяемая в методе простой итерации, для решения нелинейного уравнения:
13. Критерий останова итерационного процесса в методе простой итерации для решения нелинейного уравнения:
Итерационный процесс заканчивается, если для каждой i-й компоненты вектора неизвестных будет выполнено условие достижения точности.
Заметим, что точное решение в методе простой итерации никогда не будет достигнуто, однако с каждой последующей итерацией вектор неизвестных все ближе приближается к точному решению
14. Критерий выбора вспомогательной функции F(x) для итерационного отрезка интервала :
Выполняя контрольную по математике на решение метода простой итерации сначала обязательно производят проверку условия сходимости. Для сходимости метода необходимо и достаточно, чтобы в матрице А абсолютные значения всех диагональных элементов были больше суммы модулей всех остальных элементов в соответствующей строке:
Недостатком итерационных методов является это достаточно жесткое условие сходимости, которое выполняется далеко не для всех систем уравнений.
Если условие сходимости выполнено, то на следующем этапе необходимо задать начальное приближение вектора неизвестных, в качестве которого обычно выбирается нулевой вектор:
15. Метод Гаусса, применяемый для решения систем линейных уравнений, предусматривает:
Метод основан на преобразовании матрицы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы.
Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:
2. Матрица исходной системы не всегда имеет диагональное преобладание. В таких случаях систему можно преобразовать. Уравнения, удовлетворяющие условию сходимости, оставляют нетронутыми, а с неудовлетворяющими составляют линейные комбинации, т.е. умножают, вычитают, складывают уравнения между собой до получения нужного результата.
Если в полученной системе на главной диагонали находятся неудобные коэффициенты, то к обеим частям такого уравнения прибавляют слагаемые вида с i *x i, знаки которых должны совпадать со знаками диагональных элементов.
3. Преобразование полученной системы к нормальному виду:
i = b i /a ii
Следует снова убедиться, что полученная система нормального вида соответствует условию сходимости:
∑ (j=1) |α ij |≤ 1, при этом i= 1,2. n
4. Начинаем применять, собственно, сам метод последовательных приближений.
Вычисляем, пока не достигнем требуемой точности:
max |x i (k)-x i (k+1) ≤ ε
Итак, давайте разберем на практике метод простой итерации. Пример:
Решить СЛАУ:
Посмотрим, преобладают ли по модулю диагональные элементы.
Мы видим что условию сходимости удовлетворяет лишь третье уравнение. Первое и второе преобразуем, к первому уравнению прибавим второе:
Из третьего вычтем первое:
Мы преобразовали исходную систему в равноценную:
Теперь приведем систему к нормальному виду:
Проверяем сходимость итерационного процесса:
0,3947
Начальное приближение х (0) = 0,4762
0,8511
Подставляем данные значения в уравнение нормального вида, получаем следующие значения:
0,08835
x (1) = 0,486793
0,446639
Подставляем новые значения, получаем:
0,215243
x (2) = 0,405396
0,558336
Продолжаем вычисления до того момента, пока не приблизимся к значениям, удовлетворяющим заданному условию.
Проверим правильность полученных результатов:
Результаты, полученные при подстановке найденных значений в исходные уравнения, полностью удовлетворяют условиям уравнения.
Как мы видим, метод простой итерации дает довольно точные результаты, однако для решения этого уравнения нам пришлось потратить много времени и проделать громоздкие вычисления.
В координатной форме записи метод Зейделя имеет вид:
Таким образом i-тая компонента (k+1)-го приближения вычисляется по формуле
Условие окончания итерационного процесса Зейделя при достижении точности ε в упрощенной форме имеет вид:
Для решения систем A x = b с трехдиагональной матрицей наиболее часто применяется метод прогонки, являющийся адаптацией метода Гаусса к этому случаю.
Запишем систему уравнений
в матричном виде: A x = b где
A= 
Выпишем формулы метода прогонки в порядке их применения.
1. Прямой ход метода прогонки (вычисление вспомогательных величин):
2. Обратный ход метода прогонки (нахождение решения):
Метод простых итерации
Суть метода простых итераций состоит в переходе от уравнения
к эквивалентному уравнению
где b = const, при этом корни исходного уравнения не изменятся.
т.е. общая схема итерационного процесса:
Наиболее простой критерий окончания процесса
РЕШЕНИЕ СЛАУ ИТЕРАЦИОННЫМИ МЕТОДАМИ И ИХ ПРЕИМУЩЕСТВА
Численное решение систем линейных алгебраических уравнений (СЛАУ) – одна из наиболее часто встречающихся задач в научно-технических исследованиях, математической физике, экономике, статистике. Все используемые на практике методы решения СЛАУ можно разделить на две группы: точные методы и итерационные методы.
Преимуществом итерационных методов является удобное применение в современной вычислительной технике, т.к. решения, полученные с помощью прямых методов, обычно содержат погрешность. Итерационные методы же позволяют получить решение данной системы с заранее заданной точностью.
Суть итерационных методов решения систем заключается в том, что СЛАУ AX=B мы приводим к итерационной форме X=φX. Задаем начальное приближение значений решений X0 и решение системы ищем в виде последовательности Xk+1=φXk, постепенно улучшающихся приближений. Итерационный процесс должен быть сходящимся и его продолжают до тех пор, пока два последовательных приближения не совпадут в пределах заданной точности. Примером обычных итерационных методов служат: метод итераций (метод Якоби), метод Зейделя, метод верхних релаксаций.
Мы подробнее остановимся на итерационном методе Зейделя, т.к. этот метод является одним из самых распространенных и наиболее легко программируемых.
Он представляет собой некоторую модификацию метода простых итераций. Идеей этого метода, а самое главное его особенностью является то, что полученное в первом уравнении значение сразу же используется во втором, а значения первого и второго – в третьем и т. д. Итерационный процесс продолжается до тех пор, пока значения неизвестных не станут отличаться от предыдущих приближений на заданную точность ε.
Мы рассмотрели применение метода Зейделя к решению системы
21.9x1 +2.2×2 +3.1×3 +1.9×4 = 25.702.2×1+22.2×2+2.5×3+3.5×4=31.463.1×1+2.5×2+20.8×3+2.3×4=32.761.9×1+3.5×2+2.3×3+33.1×4=53.72 с точностью ε = 0,0001.
В данной системе наблюдаем преобладание диагональных коэффициентов, что является достаточным условием сходимости метода Зейделя. Приведем систему к виду X=φX и запишем итерационную формулу
x1k+1=121.9 ∙25.70-2.2 x2k-3.1 x3k-1.9 x4k x2k+1=122.2∙31.46-2.2 x1k+1-2.5 x3k-3.5 x4k x3k+1=120.8∙32.76-3.1 x1k+1-2.5 x2k+1-2.3 x4k x4k+1=133.1∙53.72-1.9x1k+1-3.5x2k+1-2.3x3k+1
В ходе работы была написана программа в среде программирования Cu++ по реализации решения СЛАУ методом Зейделя. В качестве начального вектора выбрали свободные члены системы: X0=1.17;1.42;1.58;1.62T. Оказалось, что достаточно трех итераций, чтобы получить решение данной системы с заданной точностью. В итоге мы получили следующий вектор решений X3=0.7859;0.9865;1.1855;1.3912T.
Явным преимуществом итерационных методов является значительное превосходство над точными методами по скорости, и они удобнее реализуются на практике. Использование итерационных методов с помощью ЭВМ эффективно в решении СЛАУ с разряженными матрицами, а также для уточнения решения СЛАУ, полученного с помощью прямого метода. Главным недостатком этих методов является то, что вопрос сходимости итерационного процесса требует отдельного исследования.
Турчак, Л.И., Плотников П.В. Основы численных методов: Учебное пособие. – 2-е изд., перераб. и доп. / Л.И. Турчак, П.В. Плотников/– М.: ФИЗМАТЛИТ, 2003. – 304с.
Преимущества и недостатки итерационных методов
1) имеют простую вычислительную процедуру;
2) не требуют сложных специальных процедур для экономии памяти ЭВМ под нулевые элементы матрицы коэффициентов, как метод Гаусса;
3) самоисправление ошибок.
1) не всегда могут решить систему уравнений (требуется выполнение условий сходимости)
2) сходимость итерационных процессов может быть медленной;
3) корни системы могут быть определены только приближенно с точностью ε.
ТЕМА 2.2 РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Понятие о системах нелинейных уравнений
И методах их решения
Для примера приведем нелинейные уравнения балансов мощностей в узлах электрической сети, составленных по методу узловых напряжений (без вывода).
Рнi и Qн i — активная и реактивная мощности нагрузки в i-м узле;
Уравнения балансов активных и реактивных мощностей в узле i
 ; |
 , |
где 
означает, что узел j‚ принадлежит множеству всех узлов, которые связаны с узлом i.
Формулы для потоков активной и реактивной мощностей от узла к узлу j следующие:
Применяются две системы координат, в которых могут проводиться расчеты:
1) прямоугольная система координат (в комплексном виде);
2) полярная система координат (через тригонометрические функции).
В полярной системе координат выражения для потоков мощности имеют следующий вид:
 |
 |
где 
;
;
Y – заданные проходимости схемы замещения системы;
P, Q, U, 
— параметры режима, часть из них известна (обычно это мощности нагрузок в узлах, напряжение и угол в базисном узле), остальные являются искомыми переменными, которые следует определить в результате расчета.
Подчеркнем, что нелинейность в уравнениях выражается как наличием в них степеней второго порядка, так и наличием тригонометрических функций.
Для решения систем нелинейных уравнений используются только итерационные методы. В том числе для решения систем нелинейных уравнений могут использоваться методы простой итерации и Зейделя при условии их сходимости.
Пример: дана система нелинейных уравнений
;
.
Приведем к виду удобному для итерации
;
.
Результаты расчетов обоими методами сведем в таблицу (ε=0,001)
Метод простой итерации
Нелинейные уравнения, составленные для расчетов режимов, обычно сложнее чем в приведенном примере и их не всегда можно решить этими методами. Гораздо лучшую сходимость для решения нелинейных уравнений и вследствие этого большее применение имеет метод Ньютона. Но этот метод имеет более сложную вычислительную процедуру.
Метод Ньютона /2/ (называемый также методом линеаризации или методом касательных) применяется для решения системы нелинейных уравнений. Он эффективен, если известно достаточно хорошее приближение к корням системы нелинейных уравнений.
Недостатком итерационных методов является то что для каждого рекуррентного процесса
Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.
На первом шаге этого метода находится максимальный по модулю коэффициент при неизвестном среди всех элементов расширенной матрицы. Пусть этот элемент располагается на пересечении p-й строки и q-го столбца. Этот элемент apq называется главным элементом, а строка с номером p называется главной строкой.
С новой расширенной матрицей проводится аналогичная операция.
Новый главный элемент выбирается среди всех столбцов, кроме самого правого, который состоит из преобразованных свободных членов. Новая главная строка перемещается на второе место вслед за первой главной.
Соответствующая расширенная матрица имеет вид:
Затем главную строку умножим на отношение a22/a32 = 0,2766 и вычтем ее из 2-й строки матрицы (4.26). Вычисления показывают, что вторые элементы в преобразованных строках занулятся. Отбрасывая этот столбец, получаем новую матрицу размером 32:
Теперь не составляет труда последовательно вычислить корни данной системы обратным ходом, описанным в предыдущем параграфе:
x1 = 1,331; x2 = 0,693; x3 = 1,802.
Результаты целесообразно округлить до 0,001 (хотя исходные данные были записаны с точностью до 0,01) и затем провести проверку подстановкой полученных корней в исходную систему уравнений.
Расчет методом главных элементов является несколько более трудоемким по сравнению с обычным методом Гаусса, рассмотренным в §4.3, так как требует на каждом шаге прямого хода совершать поиск главного элемента. Это не является серьезным недостатком метода, так как его реализация проводится на современных компьютерах.
Вышеприведенный пример 2 не демонстрирует преимуществ метода главных элементов из-за малого размера решаемой системы. Однако при большом количестве уравнений метод главных элементов позволяет добиться требуемой точности искомых корней без проведения операции уточнения и, следовательно, является более эффективным относительно обычного метода Гаусса.
На точность решения системы линейных уравнений существенно влияют, помимо выше рассмотренных факторов, погрешности исходных данных: коэффициентов матрицы А и свободных членов b.
Для наглядности рассмотрим геометрические представление системы линейных двух уравнений с двумя неизвестными a11 x1 + a12 x2 = b1, a21 x1 + a22 x2 = b2. (4.29) Каждое уравнение последней системы можно изобразить прямой линией в системе координат x1, x2 (см. рис. 4.1).
xxxx а б Рис. 4.1. Геометрическая схема решения системы двух линейных уравнений с двумя неизвестными.
Корни системы (4.29) на рис. 4.1 представлены координатами точки пересечения прямых линий. Изменение коэффициентов при неизвестных и свободных членов системы (4.29) изобразится сдвигом или поворотом линий. Из рис. 4.1.а видно, что малые изменения величин aij и bi (i, j = 1, 2) приведут к небольшому сдвигу точки пересечения. Напротив, в случае, изображенном на рис. 4.1.б точка пересечения может переместиться очень сильно даже при малом возмущении чисел aij и bi (i, j = 1, 2).
Чувствительность решения системы линейных уравнений (4.1) к изменению коэффициентов при неизвестных и свободных членов характеризуется с помощью числа обусловленности cond(A).
Для определения этой величины обусловленности сначала требуется ввести понятие нормы вектора и матрицы. В линейной алгебре используются различные варианты определения норм. В настоящем учебном пособии нормой n-мерного вектора полагается сумма абсолютных значений элементов этого вектора. Например, норма вектора свободных членов системы (4.1) запишется в виде:
n || b || = bi. (4.30) i=За норму матрицы примем максимальное значение из норм векторов, образованных столбцами этой матрицы. Норма матрицы коэффициентов при неизвестных (4.2) выразится так:
|| А || = max || aj ||, (4.31) j=1. n где aj – вектор, состоящий из элементов j-го столбца матрицы А.
Числом обусловленности матрицы А называется величина cond(A) = || А || || А-1 || (4.32) В теории систем линейных уравнений доказывается, что всегда cond(A) 1.
Обозначим b вектор погрешностей свободных членов, x – вектор погрешностей корней. В теории получено следующее соотношение:
x b cond(A). (4.33) x b Если число обусловленности cond(A) много больше единицы, то матрица A называется плохо обусловленной. При этом сравнительно малые относительные погрешности свободных членов могут привести к большим погрешностям корней.
Обозначив A матрицу погрешностей коэффициентов при неизвестных исходной системы линейных уравнений (4.1), можно записать соотношение, которое выражает влияние погрешностей исходных данных на точность корней системы (4.1):
x A b cond(A) +. (4.34) x A A b 1- cond(A) A Заметим, что для вычисления числа обусловленности необходимо иметь явный вид обратной матрицы А-1. Существуют специальные способы приближенной оценки числа cond(A), которые не требуют использования А-1. Эти приемы описаны в подробных курсах численных методов, например в [5].
Для решения плохо обусловленных систем линейных уравнений применяются особые методы, изложенные в специальных курсах и учебных пособиях.
§ 4.5. Итерационные методы Как было указано в начале данной главы, итерационные методы представляют собой методы последовательных приближений. Каждый итерационный метод использует определенное рекуррентное соотношение. По заданному нулевому приближению сначала вычисляется первое, затем по первому второе и т.д. Процесс итераций должен быть построен таким образом, чтобы с ростом числа шагов получаемые приближенные значения корней в принципе сходились к точному решению.
Следует иметь в виду, что исходные данные – коэффициенты при неизвестных и свободные члены в практических задачах часто обладают неустранимой погрешностью. Кроме того, в процессе расчетов на компьютере неизбежны погрешности округления из-за конечной разрядности регистров процессора. В этой связи важным достоинством итерационных методов является то, что можно заранее задать точность искомого решения. Главный же их недостаток – то, что для каждого рекуррентного процесса необходимо исследование условий его сходимости.
Вновь рассмотрим систему линейных уравнений (4.1).
Предположим, что все диагональные коэффициенты матрицы А не равны нулю aii 0 (i= 1, 2. n). Разрешим первое уравнение относительно неизвестного x1, второе уравнение – относительно x2 и т.д.
В результате получим систему линейных уравнений, эквивалентную данной (4.1).
x1 = d1 + c12 x2 + c13 x3 +. + c1n xn, x2 = d2 + c21 x1 + c23 x3 +. + c2n xn. ……………… (4.35) xn = dn + cn1 x1 + cn2 x2 +. + cnn-1 xn-1.
В последней системе введены новые обозначения:
nc cn2. cnn и вектор-столбец D d d D =. (4.39).
n d Перепишем систему (4.35) в матричной форме x = D + C x. (4.40) Решить систему (4.40) можно методом простой итерации (методом Якоби). Для этого примем вектор D за начальное приближение вектора x(0) искомых корней. Тогда, подставляя в правую часть уравнений (4.40) вектор x(0), получим в левой части векторстолбец первого приближения корней:
Последовательно повторяя эту операцию, вычисляем (k+1)-е приближения с помощью следующего рекуррентного матричного соотношения:
x(k+1) = D + C x(k). (4.41) Распишем формулы последовательных приближений в развернутом виде:
n xi(0) = di, xi(k +1) = di + x(k ), (4.42) ij j c j=где i = 1, 2. n ; k = 0, 1, 2.
Метод простой итерации основан на том, что последовательность векторов-столбцов x(k) (k = 0, 1, 2. ) сходится к точному решению исходной системы (4.1) при определенных условиях, которые будут сформулированы ниже.
Достаточное условие сходимости итерационного процесса (4.41) может быть выражено в виде:
Из определения нормы матрицы следует, что условие (4.43) у матрицы C выполнится, если ее элементы малы по абсолютной величине. Это достигается, если диагональные элементы aii достаточно велики по модулю относительно остальных элементов aij (i j) матрицы А, что следует из определения (4.36). Можно доказать, что условие сходимости (4.43) будет выполнено, если справедливы n неравенств:
n | aii | > aij, i = 1, 2. n. (4.44) j =j i Иначе говоря, метод простой итерации даст единственное решение системы линейных уравнений (4.1), если в каждом уравнении модуль диагонального коэффициента превышает сумму модулей остальных коэффициентов в соответствующей строке исходной системы, т.е.
сумму модулей остальных коэффициентов при неизвестных в этом уравнении.
Выполнить требование (4.44) можно, применяя линейные преобразования уравнений исходной системы (4.1).
Пример 3. Дана следующая система из 4-х линейных уравнений:
Для всех уравнений последней системы выполнены условия (4.44).
Можно эту систему преобразовывать к виду (4.35) и решать методом простой итерации (4.41).
В качестве иллюстрации скорости сходимости итерационного процесса (4.41) еще один пример.
Пример 4. Пусть система состоит из трех следующих линейных уравнений.
Видно, что для данной системы условие (4.44) выполнено и, следовательно, можно для решения применить метод простой итерации.
Сначала преобразуем систему (4.45) к стандартному виду (4.35):
В качестве начального приближения возьмем вектор свободных ( ( ( членов системы уравнений (4.46): x10) = 2; x20) = 3; x30) = 5.
Подставляя эти числа в правые части уравнений (4.46), получим в левых частях первое приближение решения. Результаты нескольких итераций сведены в следующую таблицу 4.1.
Значения, приведенные в таблице 4.1, показывают, что решение системы линейных уравнений (4.45) с точностью до пяти знаков после запятой достигается уже после 4-й итерации. Последующие итерации не изменяют значения указанных десятичных разрядов. Если требуется вычислить корни с точностью до 0,001, то достаточно провести лишь итерации. Полученное решение будет достаточно точным в рамках заданной погрешности.
Таблица 4.Номер x1 x2 xитерации 0 2 3 1 1,92 3,19 5,2 1,9094 3,1944 5,3 1,909228 3,194948 5,4 1,909199 3,194963 5,5 1,909198 3,194964 5,Пример 4 демонстрирует, что после преобразования исходной системы к виду (4.35) остается проводить операции умножения и сложения, вычисляя правые части этой системы. Хранить в оперативной памяти компьютера приходится только неизменяемую матрицу C.
Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.
