Недостатком итерационных методов является то что для каждого рекуррентного процесса
Преимущества и недостатки итерационных методов
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/ (называемый также методом линеаризации или методом касательных) применяется для решения системы нелинейных уравнений. Он эффективен, если известно достаточно хорошее приближение к корням системы нелинейных уравнений.
Итерационные методы решения системы линейных алгебраических уравнений
В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.
Общие сведения об итерационных методах или методе простой итерации
Метод итерации — это численный и приближенный метод решения СЛАУ.
Метод Якоби
Элементы (компоненты) вектора d вычисляются по следующей формуле:
Расчетная формула метода простой итерации:
x ( n + 1 ) = B x ( x ) + d
Матричная запись (координатная):
Критерий окончания в методе Якоби:
Решить СЛАУ методом Якоби:
Приводим СЛАУ к удобному виду для итерации:
В таком случае, первая итерация имеет следующий внешний вид:
Аналогичным способом вычисляются приближения к решению:
Далее вычисляем нормы разности векторов:
Метод Зейделя
Метод Зейделя — метод является модификацией метода Якоби.
За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.
Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.
Решим 3 системы уравнений:
Приведем системы к удобному для итерации виду:
Отличительная особенность, условие сходимости выполнено только для первой системы:
Вычисляем 3 первых приближения к каждому решению:
Итерационный процесс разошелся.
Итерационный процесс зациклился.
Метод простой итерации
Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:
Расчетная формула имеет следующий внешний вид:
Особенности и преимущества итерационных методов решения систем линейных алгебраических уравнений
План
Лекция 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, при этом корни исходного уравнения не изменятся.
т.е. общая схема итерационного процесса:
Наиболее простой критерий окончания процесса
Недостатком итерационных методов является то что для каждого рекуррентного процесса
Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 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 рабочих дней удалим его.