Методы приближенного решения линейных уравнений

Приближённые методы решения СЛАУ

Лекция 1

Приближённые методы решения СЛАУ

А) Метод простых итераций.(Метод последовательных приближений).

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

(1)

или где — заданные числа; .

Задаются произвольно n-чисел – нулевое приближение искомой функции.

Далее подставляем в правую часть системы (1) нулевое приближение и

находим первое приближение.

, (2)

Затем по 1-ому приближению находят 2-ое, 3-е и т.д.

В результате для k-ого приближения получаем формулу:

, (2’)

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

Х (0) ,Х (1) ,…, Х (К) , к=1,2,…

Если любая из таких последовательностей <Х_i (к) > сходится некоторому пределу x_i k = c_i , ,то данный вектор с_i, является решением сист. (1)

В равенстве (2’) перейдем к пределу при k→∞ при замене х_i на с_i.

Теорема(достаточные условия сходимости простой итерации):

Пусть выполняется хотя бы одно из следующих условий (нормы матрицы):

а) Если максимум суммы модулей коэффициентов при неизвестных (по строкам) меньше 1:

б) Если максимум суммы модулей коэффициентов при неизвестных (по столбцам) меньше 1:

в) Если сумма всех элементов в квадрате меньше 1.

Если выполняется хотя бы одно, тогда справедливы утверждения:

1)система (1) имеет единственное решение (С₁. С_n);

2)последовательность , где i = определяется по формуле (2), при любом начальном приближении сходится к соответствующим компонентам точного решения. i =

3)для приближенного равенства верны оценки (x₁ ( k ) ,…x_n ( k ) ) (C_1,…C_n),

а’) есливыполняется условие а), то

,

б’) если выполняется условие б), то

,

в’) если выполняется условие в), то

.

Замечания:

1)Если нет никакой информации о точном решении СЛАУ, то за начальное приближение выбираем столбец свободных коэффициентов. (из приведенной матрицы);

2)остановка вычислений производной по заданной величине абсолютной погрешности и приведенным в теореме оценкам.

Б) Метод Зейделя.

Этот метод является модификацией МПИ и заключается в том, что при вычислении (к+1) приближения неизвестного х_i (i>1), используются уже вычисленные ранее (к+1) приближения неизвестных х₁, х₂,…, х_i-1

Рассмотрим систему: i=1,n

Пусть матрица α удовлетворяет одному из условий теоремы:

Если, а) j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i

Прямой ход.

Это основной этап решения системы уравнений с помощью метода Гаусса. Его суть состоит в приведении исходной расширенной матрицы системы к верхнетреугольной матрице с помощью эквивалентных преобразований (добавление к строке любой линейной комбинации других строк и перестановка строк, т.е. уравнений). Формулы прямого хода соответствуют последовательному выражению переменных из уравнений и подстановке их в последующие уравнения, т.е. их фактическому исключению из последующих уравнений системы. При этом шагом считается исключение одной переменной из всех последующих уравнений системы.

Рассмотрим k-ый шаг прямого хода. На k-ом шаге матрица системы имеет вид:

Осталось n-k+1 неизвестных. Чтобы удалить х(k) из последней строчки, например, надо из нее вычесть k-ую строчку с таким коэффициентом, чтобы получить на месте а_nk ноль. Для этого коэффициент должен быть равен c_nk=a_nk/a_kk. Элемент а_kk называется разрешающим элементом k-ого шага и должен быть отличен от 0.

Формулы прямого хода

c_mk=a_mk/a_kk где 1

,откуда получаем:

Лекция 2.

Выбор шага

1. Пусть требуется вычислить интеграл с точностью ε. Используя формулу соответствующего остаточного члена R, выбирают h таким образом, чтобы выполнялось неравенство .

2. Двойной пересчёт. ( Правило Рунге).

Лекция 4

ЧИСЛЕННОЕ РЕШЕНИЕ ТРАНСЦЕНДЕНТНЫХ И НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

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

Процесс нахождения приближённых значений корней уравнения:

f(x) = 0, (1)

где функция f(x) определена и непрерывна в некотором конечном или

бесконечном интервале a n раз. Таким образом, число итераций n в данном методе зависит от предварительно заданной точности ε и от длины исходного отрезка и не зависит от вида функции f(x). Это является важным преимуществом метода половинного деления по сравнению с другими методами. Метод, однако, медленно сходится при задании высокой точности расчёта.

Метод хорд.

Пусть на отрезке [a,b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ′(x) и f ″(x) сохраняют постоянный знак на интервале (a,b). Тогда возможны четыре случая расположения дуги кривой (рис.4).

Рис.4.

В методе хорд за очередное приближение берём точку пересечения с осью Х прямой (рис.5), соединяющей точки (a,f(a)) и (b,f(b))

Причём одна из этих точек фиксируется − та, для которой знаки f(x) и f ″(x) одинаковы.

Для рис.5 неподвижным концом хорды является х =a.

Уравнение хорды АВ:

Точка пересечения хорды с осью Х (у=0): .

Теперь корень находится на отрезке [a,c₁]. Заменяем b на с₁.

Рис.5. Иллюстрация метода хорд.

Применяя метод хорд к этому отрезку, получим:

.

Продолжим и т.д., получим: (2) Условие окончания вычислений:

│с_n+1 − c_n│ 0, то приближённое значение корня находят по формуле (2), если f′(x)∙f″(x) ( n ) ) = 0 или .

Определение: Порядком дифференциального уравнения называется порядок наивысшей производной, входящей в уравнение.

у′-2ху 3 +5=0—— уравнение первого порядка,

у″+ky′-by-sinx=0—— уравнение второго порядка.

Задача Коши (для уравнения первого порядка):

у′ = f(x, y) (1) найти решение y = y(x),

удовлетворяющее начальному условию: у(х₀)=у₀. (1*).

Т.е. найти интегральную кривую, проходящую через точку М(х₀, у₀).

Если f(x,y) непрерывна в области R: |x-x₀| ( n ) =f(x,y,y′,…,y ( n -1) ) задача Коши состоит в нахождении решения у = у(х), удовлетворяющего начальным условиям:

у(х₀) = у₀, у′(х₀) = у′₀, …, у ( n -1) (x₀) = y ( n -1) ₀ ― заданные числа.

Функция у = f(x, C₁, C₂,…, C_n), где С₁,…, С_n― произвольные постоянные, называется общим решением ОДУ или общим интегралом.

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

Определение: задача называется краевой, если указывается интервал интегрирования [a,b] и ставятся дополнительные условия для значений функции у и её производных на концах этого интервала.

Процесс познания закономерностей и стремление создать детальную картину исследуемых явлений приводит к более сложной количественной оценке, отражающей эти явления, а именно к функции многих переменных, зависящих как от пространственных координат, так и от времени u = f(x₁, x₂,…, x_n, t).

Определение: Дифференциальным уравнением с частными производными называется уравнение, связывающее независимую переменные х₁, х₂, …, х_n, t, искомую функцию

u = f (х₁, х₂, …, х_n, t) и её частные производные:

.

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

Дано дифференциальное уравнение первого порядка: у′ = f(x,y) (1).

Требуется найти решение этого уравнения на отрезке [x₀, x_max], удовлетворяющее начальным условиям: у(х₀) = у₀ (2).

В вычислительной практике более предпочтительным являются численные методы нахождения приближённого решения в фиксированных точках: х₀ 1 и b₀ = 0 ― явными многошаговыми.

― при r > 1 и b₀ ≠ 0 ― неявными многошаговыми.

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

А) Метод Эйлера.

Для решение Д.У.(1) с Н.У. (2) на отрезке [x₀, x_max] по методу Эйлера, таблица приближённых значений у(х) для равноотстоящих узлов:

Абсолютная погрешность формулы (4) на каждом шаге имеет порядок h 2

(5)

Формула (4) означает, что на отрезке [x_k, x_k+1] интегральная кривая y = y(x) приближённо заменяется прямолинейным отрезком, выходящим из точки М(х_k;у_k) с угловым коэффициентом f(х_k;у_k). В качестве приближения искомой интегральной кривой получаем ломаную линию с вершинами в точках М₀(х₀;у₀), М₁(х₁;у₁),…, М_n(х_n;у_n). Первое звено касается истинной интегральной кривой в точке М₀(х₀;у₀).

Метод Эйлера может быть применён к решению системы ОДУ и ДУ высших порядков. Последние должны быть предварительно приведены к системе ОДУ первого порядка.

Пусть задана система ОДУ первого порядка: (6)

Приближённые значения у(х_i) ≈ y_i, z(х_i) ≈ z_i вычисляются по формулам:

(8)

Метод Эйлера обладает двумя существенными недостатками:

1) малой точностью (метод первого порядка точности);

2) систематическое накопление ошибок.

В) Модификации метода Эйлера.

1 ый усовершенствованный метод Эйлера.

Сначала вычисляют промежуточные значения:

(9)

А затем полагают: (10)

2 o й усовершенствованный метод Эйлера.

Сначала определяют «грубые приближения»: (11)

И приближённо полагают: (12)

Локальная погрешность на i-ом шаге: . Оценка погрешности в точке х_n может быть получена с помощью двойного просчёта (с шагом h и h/2):

(13)

С.) Метод Рунге-Кутта. (4 го порядка)

Наиболее знаменитым из методов Рунге-Кутта является классический метод 4 го порядка

(14)

(15)

Грубая оценка погрешности (двойной просчёт): (16)

Где у(х_i) – точное решение, у * _i – приближённое решение с шагом h/2, y_i – … с шагом h _.

Для оценки правильности выбора шага h используют равенство:

(17)

q должно равняться нескольким сотым, иначе h уменьшается.

D). Метод Рунге–Кутта 3-го порядка

Многошаговые методы.

(используют информацию о нескольких предыдущих точках)

Д ) Алгоритм Адамса.

Пусть дано дифференциальное уравнение: у′ = f(x, y) (1)

с начальными условиями: у(х₀) = у₀ (1*)

Требуется найти решение уравнения (1) на отрезке [a,b].

Разобьём отрезок [a,b] на n равных частей точками х_i = х₀ + ih (i =0, 1, …, n).

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

2 ой этап: рекурсивной процедуры. Определение: у_k, y_k+1,…, y_n основано на интегрировании интерполяционного многочлена Ньютона.

Рабочие формулы явных методов Адамса (2-го, 3-го, 4-го порядков).

(2)

(3)

(4)

Формулы (2)-(4) называются экстраполяционными и на практике используются в качестве прогноза.

Для улучшения точности или коррекции результата применяют неявные методы (используют ещё ненайденные значения: у_k+1, y_k+2,…).

(5)

(6)

(7)

Формулы (5)-(7) называются интерполяционными.

Для грубой оценки точности (двойной просчёт):

Лекция 1

Приближённые методы решения СЛАУ

А) Метод простых итераций.(Метод последовательных приближений).

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

(1)

или где — заданные числа; .

Задаются произвольно n-чисел – нулевое приближение искомой функции.

Далее подставляем в правую часть системы (1) нулевое приближение и

находим первое приближение.

, (2)

Затем по 1-ому приближению находят 2-ое, 3-е и т.д.

В результате для k-ого приближения получаем формулу:

, (2’)

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

Х (0) ,Х (1) ,…, Х (К) , к=1,2,…

Если любая из таких последовательностей <Х_i (к) > сходится некоторому пределу x_i k = c_i , ,то данный вектор с_i, является решением сист. (1)

В равенстве (2’) перейдем к пределу при k→∞ при замене х_i на с_i.

Теорема(достаточные условия сходимости простой итерации):

Пусть выполняется хотя бы одно из следующих условий (нормы матрицы):

а) Если максимум суммы модулей коэффициентов при неизвестных (по строкам) меньше 1:

б) Если максимум суммы модулей коэффициентов при неизвестных (по столбцам) меньше 1:

в) Если сумма всех элементов в квадрате меньше 1.

Если выполняется хотя бы одно, тогда справедливы утверждения:

1)система (1) имеет единственное решение (С₁. С_n);

2)последовательность , где i = определяется по формуле (2), при любом начальном приближении сходится к соответствующим компонентам точного решения. i =

3)для приближенного равенства верны оценки (x₁ ( k ) ,…x_n ( k ) ) (C_1,…C_n),

а’) есливыполняется условие а), то

,

б’) если выполняется условие б), то

,

в’) если выполняется условие в), то

.

Замечания:

1)Если нет никакой информации о точном решении СЛАУ, то за начальное приближение выбираем столбец свободных коэффициентов. (из приведенной матрицы);

2)остановка вычислений производной по заданной величине абсолютной погрешности и приведенным в теореме оценкам.

Б) Метод Зейделя.

Этот метод является модификацией МПИ и заключается в том, что при вычислении (к+1) приближения неизвестного х_i (i>1), используются уже вычисленные ранее (к+1) приближения неизвестных х₁, х₂,…, х_i-1

Рассмотрим систему: i=1,n

Пусть матрица α удовлетворяет одному из условий теоремы:

Если, а) j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i

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

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

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

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

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня 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 ) .

Метод итераций решения системы уравнений. Пример решения

Решение получаем с помощью калькулятора Решение СЛАУ методом итераций .

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

Прежде чем применять метод итераций, необходимо переставить строки исходной системы таким образом, чтобы на диагонали стояли наибольшие по модулю коэффициенты матрицы. Если при этом условие все таки не выполняется, то иногда удается обеспечить сходимость метода с помощью следующего метода.
Пусть дана система Ax = b. Преобразуем ее к виду: x= Qx + c
где Q = E — D•A, c = D•b
Здесь D — некоторая матрица. Нам необходимо подобрать такую матрицу D, чтобы выполнялось условие |Q| 0 =β, тогда:
x 1 =b — a x 0
x 2 =b — a x 1
.
x k+1 =b — a x k
Для нашей задачи достаточное условие сходимости выполняется.

Приведем к виду:
x₁=0.5-(0.2x₂-0.1x₃)
x₂=-4.07-(0.33x₁+0.17x₃)
x₃=3-(0.0833x₁-0.25x₂)
Покажем вычисления на примере нескольких итераций.
N=1
x₁=0.5 — 0 • 0.2 — 0 • (-0.1)=0.5
x₂=-4.07 — 0 • 0.33 — 0 • 0.17=-4.07
x₃=3 — 0 • 0.0833 — 0 • (-0.25)=3
N=2
x₁=0.5 — (-4.07) • 0.2 — 3 • (-0.1)=1.61
x₂=-4.07 — 0.5 • 0.33 — 3 • 0.17=-4.74
x₃=3 — 0.5 • 0.0833 — (-4.07) • (-0.25)=1.94
N=3
x₁=0.5 — (-4.74) • 0.2 — 1.94 • (-0.1)=1.64
x₂=-4.07 — 1.61 • 0.33 — 1.94 • 0.17=-4.93
x₃=3 — 1.61 • 0.0833 — (-4.74) • (-0.25)=1.68
Остальные расчеты сведем в таблицу.

Ответ: x₁=1.64, x₂=-4.89, x₃=1.64

Пример №2 . Решить систему уравнений Ax = b с точностью 0.05 методами: 1) простой итерации; 2) Зейделя. Указание. Для обеспечения выполнения достаточного условия сходимости воспользоваться перестановкой строк в исходной системе уравнений.