Итерационный метод решения нормальных уравнений

Метод итераций

Правила ввода функции

2. Примеры
   ≡ x^2/(1+x)
   cos 2 (2x+π) ≡ (cos(2*x+pi))^2
   ≡ x+(x-1)^(2/3)

На рис.1а, 1б в окрестности корня |φ′(x)| 1, то процесс итерации может быть расходящимся (см. рис.2).

Достаточные условия сходимости метода итерации

Процесс нахождения нулей функции методом итераций состоит из следующих этапов:

1. Получить шаблон с омощью этого сервиса.
2. Уточнить интервалы в ячейках B2 , B3 .
3. Копировать строки итераций до требуемой точности (столбец D ).

Примечание: столбец A — номер итерации, столбец B — корень уравнения X , столбец C — значение функции F(X) , столбец D — точность eps .

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

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

Общие сведения об итерационных методах или методе простой итерации

Метод итерации — это численный и приближенный метод решения СЛАУ.

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .

Рассмотрим систему A x = b .

Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.

Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.

Метод Якоби

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.

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

b i j = — a i j / a i i , i , j = 1 , 2 . . . , n

Элементы (компоненты) вектора d вычисляются по следующей формуле:

d i = b i / a i i , i = 1 , 2 , . . . , n

Расчетная формула метода простой итерации:

x ( n + 1 ) = B x ( x ) + d

Матричная запись (координатная):

x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b

Критерий окончания в методе Якоби:

x ( n + 1 ) — x ( n ) ε 1 , где ε 1 = 1 — B B ε

В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:

x ( n + 1 ) — x ( n ) ε

Решить СЛАУ методом Якоби:

10 x 1 + x 2 — x 3 = 11 x 1 + 10 x 2 — x 3 = 10 — x 1 + x 2 + 10 x 3 = 10

Необходимо решить систему с показателем точности ε = 10 — 3 .

Приводим СЛАУ к удобному виду для итерации:

x 1 = — 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = — 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 — 0 , 1 x 2 + 1

Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.

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

x 1 ( 1 ) = — 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = — 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 — 0 , 1 × 1 + 1 = 1 , 01

Аналогичным способом вычисляются приближения к решению:

x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111

Находим норму матрицы В , для этого используем норму B ∞ .

Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:

x ( n + 1 ) — x ( n ) ε

Далее вычисляем нормы разности векторов:

x ( 3 ) — x ( 2 ) ∞ = 0 , 002 , x ( 4 ) — x ( 3 ) ∞ = 0 , 00002 .

Поскольку x ( 4 ) — x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.

x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .

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

Метод Зейделя — метод является модификацией метода Якоби.

Суть: при вычислении очередного ( n + 1 ) — г о приближения к неизвестному x i при i > 1 используют уже найденные ( n + 1 ) — е приближения к неизвестным x 1 , x 2 , . . . , x i — 1 , а не n — о е приближение, как в методе Якоби.

x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i — 1 x i — 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +

+ . . . + b i m x m ( n ) + d i

За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.

Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.

Решим 3 системы уравнений:

2 x 1 + x 2 = 3 x 1 — 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 — x 2 = 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1

Приведем системы к удобному для итерации виду:

x 1 ( n + 1 ) = — 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = — 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) — 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .

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

Вычисляем 3 первых приближения к каждому решению:

1-ая система: x ( 0 ) = 1 , 5 — 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109

Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.

2-ая система: x ( 0 ) = 3 — 1 , x ( 1 ) = 5 9 , x ( 2 ) = — 15 — 31 , x ( 3 ) = 65 129

Итерационный процесс разошелся.

Решение: x 1 = 1 , x 2 = 2

3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 — 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2

Итерационный процесс зациклился.

Решение: x 1 = 1 , x 1 = 2

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

Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

x = x — τ ( A x — b ) , τ — итерационный параметр.

Расчетная формула имеет следующий внешний вид:

x ( n + 1 ) = x ( n ) — τ ( A x n — b ) .

Здесь B = E — τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .

Пусть λ m i n и λ m a x — максимальные и минимальные собственные значения матрицы А .

τ = 2 / ( λ m i n + λ m a x ) — оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n — λ m a x ) .

Итерационные методы решения систем уравнений установившегося режима

Общая характеристика методов

Методы решения систем уравнений — прямые (точные) и итерационные (приближенные). Прямые применяются для решения систем линейных урав-нений, итерационные — для решения систем линейных и нелинейных уравне-ний.

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

Суть итерационных методов: задается некоторое начальное прибли-жение неизвестных U (0) , которое постепенно уточняется в ходе выполнения ряда однотипных шагов вычислений (итераций). Если итерационный про-цесс сходится, то получаем искомое решение U (*) с заданной точностью.

Итерациями называются многократно повторяющиеся однотипные ша-ги вычислений.

Основные характеристики итерационных методов:

1. Условия сходимости к решению, при которых происходит приближе-ние к искомому решению U (*) , либо удаление от него;

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

2.3. Характер сходимости. Сходимость – апе-риодическая или колебательная.

Возможно влияние на скорость сходимос-ти за счет введения дополнительных коэффици-ентов;

4. Необходимость хранения в памяти ЭВМ всех коэффициентов систем уравнений. Удобство программирования, простота алгоритмов и т.д.

Рассматриваем систему нелинейных уравнений установившегося режи-ма. В матричной форме она имеет вид:

(1)

В развернутой форме такая система уравнений может быть представлена в следующем виде:

(2)

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

(3)

Любое i-ое уравнение этой системы можно записать в общем виде:

(4)

Если задать начальные приближения неизвестных U (0) , подставить их в правую часть уравнений (4) и выполнить необходимые вычисления, опреде-лим следующее приближение неизвестных U (1) и т.д. Такая после-довательность действий соответствует методу простой итерации. Тогда (4) в итерационной форме:

(4а)

В матричной форме система (3) может быть записана следующим образом:

здесь — вектор неизвестных напряжений;

D — вектор свободных членов, ;

С — матрица коэффициентов при неизвестных, .

В итерационном виде система (5) принимает вид:

. (6)

Здесь к – номер приближения неизвестных.

Общий алгоритм итерационных методов решения СНАУ установившегося режима

1) Задание начальных приближений вектора неизвестных U (0) =U_ном.

Как правило, в качестве начальных приближений напряжений задают номи-нальные напряжения узлов U_ном.В некоторых случаях, в качестве начальных приближений напряжений принимают значения, полученные в предыдущих близких расчетах для данной схемы;

2) Задание точности расчета E, предельного количества итераций n_пред.,

начального значения счетчика итераций к=0 и других параметров расчета;

3) Выполнение итерации в соответствии с формулой (6):

;

4) Контроль завершения итерационного процесса:

Если условие не выполняется, то изменяем счетчик итераций (к=к+1) и возвращаемся к пункту (3). Повторяем расчет при новых приближениях неизвестных.

Если условие выполняется для всех значений U_i, то итерационный процесс завершается, найденные на последней итерации приближения неизвестных U ( k +1) принимаются в качестве искомых значений с заданной точностью.

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

(7)

здесь U (* ) — точное решение при .

Таким образом, точное решение может быть получено лишь в резуль-тате бесконечного итерационного процесса. Всякий вектор U ( k ) , полученный на к-ой итерации, является приближенным решением системы уравнений.

Вектор погрешности этого приближенного решения:

(8)

Так как точное решение U (*) заранее неизвестно, то о погрешности судят по разности значений на смежных итерациях (к+1) и к, то есть по вектору поправок:

(9)

Если для всех і, то итерационный процесс завершается.

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

Более строгим и надежным способом контроля завершения итераци-онных процессов является контроль невязок уравнений. Невязка уравнения – разность между левой и правой частями уравнения. Её значение получаем при подстановке в уравнения системы (2) очередного приближения неиз-вестных. Например, для 1-го уравнения:

. (10)

Для УУР невязка уравнения соответствует расчетному небалансу тока (мощ-ности) в узле. При подстановке точных значений неизвестных U₁ (*) ,U₂ (*) ,…,U_n (*) невязки будут равны нулю:

.

То есть если итерационный процесс сошелся, то невязки близки к нулю. И чем дальше приближение U_i ( k ) от точного решения, тем больше величина не-вязок. В общем случае вектор невязок можно определить:

(11)

Итерационный процесс сошелся, если выполняются условия завершения итерационного процесса:

(12)

Это условие является более надежным критерием окончания итерационного процесса.

Достаточным условием сходимости итерационного процесса для урав-нений установившегося режима является:

Т.о. условие сходимости определяется только соотношением элементов матрицы проводимостей Y . В ней диагональные элементы У_іі (собственные проводимости узлов) неравны нулю. Как правило, диагональные элементы матрицы проводимостей больше или равны суммы недиагональных элемен-тов. Т.е. при правильном формировании матрицы, это условие сходимости выполняется всегда.

Два вида сходимости итерационных процессов:

1. Экспоненциальный (апериодический):

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

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