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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



Лекция 1

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

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

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

(1)

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

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

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

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

, (2)

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

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

, (2’)

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

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

Если любая из таких последовательностей {Хi(к)} сходится некоторому пределу xik = ci , ,то данный вектор сi, является решением сист. (1)

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

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

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

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

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

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

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

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

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

3)для приближенного равенства верны оценки (x1(k),…xn(k)) (C1,…Cn),

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

,

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

,

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

.

Замечания:

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

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

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

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

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

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

Если, а) <1 (коэффициенты по строкам)

б) <1 (коэффициенты по столбцам)

в) <1 (все коэффициенты)

 

тогда общая формула метода Зейделя имеет вид:

к=1,2…

 

Замечание: метод Зейделя обычно, но не всегда сходится к точному решения быстрее, чем МПИ

 

В) Метод Гаусса. (Метод последовательного исключения переменных)

Матрица называется верхнетреугольной, если ниже главной диагонали все элементы равны нулю, т.е. aij=0 при i>j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i<j) равны 0. Матрица называется диагональной, если только на главной диагонали (i=j) стоят ненулевые элементы. Метод Гаусса решения систем линейных уравнений состоит из двух этапов: прямого хода и обратного хода.

 

Прямой ход.

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

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

11 а12 … а1k … a1n | b1)

(0 a22 … a2k … a2n | b2)

(0 … … … … … )

(0 0 … akk … akn | bk)

(0 … … … … … )

(0 0 … ank … ann | bn)

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

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

 

cmk=amk/akk где 1<=k<n

bm=bm-cmkbk, k<m<=n

aml=aml-cmkakl, k<=l<=n

 

Обратный ход

 

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

 

Формулы обратного хода.

 

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

для k=n,n-1,…,1.

 

Лекция 2.

Выбор шага

 

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

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

 

Лекция 4

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

 

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

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

f(x) = 0, (1)

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

бесконечном интервале a < x < b разбивается на два этапа: 1) отделение корней; 2) уточнение корней до заданной степени точности.

 

Отделение корней.

 

Всякое значение λ, обращающее функцию f(x) в нуль, т. е. такое, что f(λ) = 0, называется корнем уравнения (1) или нулём функции f(x).

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

 

Графический метод отделения корней: a) строят график функции у = f(x) для уравнения вида f(x) = 0. Значения действительных корней уравнения являются абсциссы точек пересечения графика функции у = f(x) с осью Ох (рис.1);

b) представляют уравнение (1) в виде φ(х) = g(x) и строят графики функций

у = φ(х) и у = g(x). Значения действительных корней уравнения являются абсциссы точек пересечения графиков функций у = φ(х) и у = g(x) (рис.2).

Отрезки, в которых заключено только по одному корню, легко находятся.

 

 

 


Рис.1. Рис.2.

Аналитический метод отделения корней основан на следующей теореме:

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

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

 

Рис.3

 

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

После каждой итерации отрезок, на котором расположен корень уменьшается вдвое, то есть после n итераций он сокращается в 2n раз. Таким образом, число итераций 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,c1]. Заменяем b на с1.

 

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

 

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

.

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

│сn+1 − cn│< ε или │f(cn)│< ε1.

Для оценки погрешности можно пользоваться общей формулой:

, где

 

Итак, если f (x)∙f″(x) > 0, то приближённое значение корня находят по формуле (2), если f(x)∙f″(x) < 0 (т.е. фиксируется х = b), то по формуле:

 

. (3)

Лекция 5.

Приближённое решение обыкновенных дифференциальных уравнений и систем обыкновенных дифференциальных уравнений.

Пусть функция у = f(x,y) отражает количественную сторону некоторого явления. Рассматривая это явление, мы можем установить характер зависимости между величинами х и у, а также производными от у по х, т.е. написать дифференциальное уравнение.

Определение: Обыкновенным дифференциальным уравнением называется уравнение, связывающее независимую переменную х, искомую функцию y=f(x) и её производные.

Запись: F( x, y, y′, y′′,…, y(n)) = 0 или .

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

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

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

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

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

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

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

Если f(x,y) непрерывна в области R: |x-x0| < a, |y-y0| < b, то существует по меньшей мере одно решение у = у(х), определённое в некоторой окрестности: |х-х0| < h, где h ― положительное число. Это решение единственно, если в R выполнено условие Липшица: (2)

Где N― постоянная (константа Липшица), зависящая в общем случае от a и b. Если f(x,y) имеет ограниченную производную в R, то можно положить:

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

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

Функция у = f(x, C1, C2,…, Cn), где С1,…, Сn― произвольные постоянные, называется общим решением ОДУ или общим интегралом.

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

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

 

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

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

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

.

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

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

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

В вычислительной практике более предпочтительным являются численные методы нахождения приближённого решения в фиксированных точках: х0<x1<…<xn=xmax.

Большинство численных методов решения задачи (1) с начальными условиями (2) можно привести к виду: (3).

 

― при r = 1, а1 = 1, b0 = 0 методы вида (3) называются одношаговыми ( чтобы найти yi+1

требуется информация только о предыдущей точке (xi, yi)).

― при r > 1 и b0 = 0 ― явными многошаговыми.

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

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

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

х x0 x1 хn
y y0 y1 yn

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

 

строится по формулам: yk+1 = yk + h∙f(xk,yk)

xk+1 = xk + h, k = 0,…,n-1, h=(xn-x0)/n (4)

 

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

(5)

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

 

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

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

с начальными условиями: у(х0) = у0, z(х0) = z0 (7)

 

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

(8)

 

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

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

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

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

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

 

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

(9)

 

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

 

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

 

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

 

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

 

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

(13)

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

 

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

(14)

 

(15)

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

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

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

(17)

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

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

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

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

 

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

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

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

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

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

Следовательно, определены: у1, у2, …, уk-1 в точках: х0 + h, …, x0 + h(k-1).

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

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

(2)

(3)

(4)

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

 

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

(5)

(6)

(7)

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

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

 

Лекция 1

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

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

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

(1)

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

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

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

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

, (2)

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

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

, (2’)

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

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

Если любая из таких последовательностей {Хi(к)} сходится некоторому пределу xik = ci , ,то данный вектор сi, является решением сист. (1)

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

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

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

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

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

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

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

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

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

3)для приближенного равенства верны оценки (x1(k),…xn(k)) (C1,…Cn),

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

,

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

,

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

.

Замечания:

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

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

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

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

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

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

Если, а) <1 (коэффициенты по строкам)

б) <1 (коэффициенты по столбцам)

в) <1 (все коэффициенты)

 

тогда общая формула метода Зейделя имеет вид:

к=1,2…

 

Замечание: метод Зейделя обычно, но не всегда сходится к точному решения быстрее, чем МПИ

 

В) Метод Гаусса. (Метод последовательного исключения переменных)

Матрица называется верхнетреугольной, если ниже главной диагонали все элементы равны нулю, т.е. aij=0 при i>j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i<j) равны 0. Матрица называется диагональной, если только на главной диагонали (i=j) стоят ненулевые элементы. Метод Гаусса решения систем линейных уравнений состоит из двух этапов: прямого хода и обратного хода.

 

Прямой ход.

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

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

11 а12 … а1k … a1n | b1)

(0 a22 … a2k … a2n | b2)

(0 … … … … … )

(0 0 … akk … akn | bk)

(0 … … … … … )

(0 0 … ank … ann | bn)

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

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

 

cmk=amk/akk где 1<=k<n

bm=bm-cmkbk, k<m<=n

aml=aml-cmkakl, k<=l<=n

 

Обратный ход

 

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

 

Формулы обратного хода.

 

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

для k=n,n-1,…,1.

 

Лекция 2.



Последнее изменение этой страницы: 2016-04-26; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 35.172.136.29 (0.045 с.)