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

Лекция 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… Замечание: метод Зейделя обычно, но не всегда сходится к точному решения быстрее, чем МПИ Лекция 2. Интерполяция, аппроксимация. Предполагается, что функция задана в виде таблицы конечного числа точек: х х0 х1 … хn , у y0 y1 … yn например, получена экспериментально или по известной (достаточно сложной) формуле для . Здесь хi и yi (i=0,1,…, n) – произвольные числа и при этом все хi различны и упорядочены: . При этом множество всех узлов хi называют сеткой, если узлы являются равноотстоящими, т.е. хi= х0+ih, где . Используя исходные данные, затем подбирают функцию несложного вида, значения которой при являются приближенными для . Важным здесь следует отметить не только то, чтобы имела простой вид и хорошо приближала , но и чтобы ее практически можно было найти. В этом смысле наиболее подходящий вид для - многочлен . Но и в этом случае не все просто с вычислительной стороны. Как правило, при нахождении значений нельзя обойтись без многочисленных промежуточных округлений числе, что часто приводит к большой потере точности коэффициентов . И может случиться так, что полученный в результате многочлен будет гораздо хуже приближать данную функцию , чем истинный многочлен , а это недопустимо. При расчетах чаще всего нельзя заранее предсказать оптимальный режим вычислений, т.е. указать минимальную разрядность счета (начав с какой-либо) до тех пор, пока, не добьются удовлетворительных результатов, т.е. совпадения цифр в требуемых разрядах результата. Определение 1. Функция называется интерполяционной для , если выполнены условия: , i=0,1, …, n, т.е график проходит через все заданные точки . Известно, что для данной таблицы всегда существует и притом единственны интерполяционный многочлен (ИМ) степени n. Будем обозначать ИМ через . Для него верно: , i=0,1, …, n. (1) Остаточный член для , т.е. величина , имеет вид: (2) где Пn+1(x)=(x-x0)(x-x1)…(x-xn). Так как точка ξ практически всегда неизвестна, то при оценке погрешности для пользуются неравенством: . (2´) А) ИМ Лагранжа имеет вид: где . В) ИМ Ньютона ИМ Ньютона строятся на сетке и выражаются через конечные разности. Определение 2. Величина называется конечной разностью первого порядка функции в точке с шагом h. По аналогии имеем: 2-ая конечная разность – это , …, k-ая конечная разность – это . Конечные разности удобно записывать в виде таблицы 1 (в каждом столбце, кроме столбца , из последующего числа вычитается предыдущее число и разность записывается в следующем столбце). Но если является приближенным (например, из-за округлений), то в этой связи с ростом порядка конечных разностей погрешность растет (удваивается на каждом шаге). Поэтому исходные данные надо брать с повышенной точностью. Таблица 1 xi yi Δ yi Δ2 yi Δ3 yi Δ4 yi … x0 y0 Δ y0 Δ2 y0 Δ3 y0 Δ4 y0 … x1 y1 Δ y1 Δ2 y1 Δ3 y1 … x2 y2 Δ y2 Δ2 y2 … x3 y3 Δ y3 … x4 y4 … … … 1-ый ИМ Ньютона имеет вид: . (4) ИМ Ньютона играет в численном анализе роль, аналогичную роли формулы Тейлора в математическом анализе. Так при использовании формулы (4), если слагаемые, начиная с какого-то номера становятся малыми, то ими пренебрегают. Если ввести обозначение: t=(x-x0)/h, то 1-ый ИМ Ньютона примет вид: (5) 0 ≤ t ≤ n; t=(x-x0)/h Оценка погрешности: ; 0 ≤ t ≤ n; x є [x0;xn], μ=max│f(n+1)(x)│ Если ввести обозначение: t=(x-xn)/h, то получим 2-ый ИМ Ньютона: (6) ─ n ≤ t ≤ 0; t=(x-xn)/h Оценка погрешности: ; -n ≤ t ≤ 0; x є [x0;xn], μ=max│f(n+1)(x)│ С.) «МЕТОД НАИМЕНЬШИХ КВАДРАТОВ» Перечислим особенности, на которые надо обратить внимание при выполнении задания по этой теме. Предполагается, что функция задана в виде таблицы конечного числа точек хi х0 х1 … хn , уi y0 y1 … yn например, получена экспериментально, где xi, yi (i=1,…,n) – произвольные числа. При этом все числа xi различны. Пусть также имеется некоторая функция , определенная для всех значений xi (i=1,…,n). Определение 3. Число Т, где , (7) называется среднеквадратичным (или среднеквадратическим) уклонением функции от заданной . Наряду с числом Т вводят также вспомогательную величину . (8) Функцию стараются подобрать, чтобы число Т получилось достаточно малым. Можно предложить следующие способы выбора функции . Способ 1. , (9) т.е. - многочлен степени m, при этом m 0, то приближённое значение корня находят по формуле (2), если f′(x)∙f″(x) < 0 (т.е. фиксируется х = b), то по формуле: . (3) 3) Метод Ньютона (касательных). Пусть на отрезке [a,b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ′(x) и f ″(x) сохраняют постоянный знак на интервале (a,b). Геометрический смысл метода касательных состоит в том, что дуга кривой y = f(x) заменяется касательной к этой кривой. Рис.7. Иллюстрация метода касательных. Выберем в качестве начального приближения х0 = a и проведём в точке А0(a,f(a)) касательную к графику функции f(x). Абсцисса пересечения касательной с осью Ох (у = 0) является первым приближением к корню (рси.7): или х0 = . Через точку А1(х1;f(x1)) снова проведём касательную, абсцисса точки пересечения которой даст второе приближение х2 корня ξ и т.д. Очевидно, что в точке Аn(xn;f(xn)): y − f(xn) = f ′(xn)(x−xn) и алгоритм метода Ньютона запишется так: (4) Заметим, что в нашем случае, если положить х0 = b и провести касательную к кривой у = f(x) в точке b, то первое приближение не принадлежит отрезку [a,b]. Таким образом, в качестве начального приближения х0 выбирается тот конец интервала [a,b], для которого знаки f(x) и f ″(x) одинаковы. Условие окончания вычислений: │сn+1 − cn│< ε или │f(cn)│< ε1. Для оценки погрешности можно пользоваться общей формулой , где 4) Комбинированный метод (хорд и касательных). Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом, и уточнение корня происходит быстрее. Пусть дано уравнение f(x)=0, корень ξ отделён и находится на отрезке [a,b]. Применим комбинированный метод хорд и касательных с учётом типа графика функции (рис.4). Если f (x)·f ″(x) < 0 (рис.4 в, г), то методом хорд получаем значение корня с избытком, а методом касательных – с недостатком. Если f (x)·f ″(x) > 0 (рис.4 а, б), то метод хорд даёт приближение корня с недостатком, а метод касательных – с избытком. Рассмотрим случай, когда f (b) < 0, f ″(x) > 0 (рис.8), то со стороны конца а лежат приближённые значения корня, полученные по методу касательных, а со стороны конца b – значения, полученные по методу хорд. Рис.8 Иллюстрация комбинированного метода. Тогда , . Теперь истинный корень ξ находится на интервале [a1,b1]. Применяя к этому интервалу комбинированный метод, получаем , и вообще , . (5) Для случая, когда f (b)·f ″(x) > 0, то рассуждая аналогично, получим следующие формулы для уточнения корня уравнения: , . (6) Комбинированный метод очень удобен при оценке погрешности вычислений. Процесс вычислений прекращается, как только станет выполняться неравенство ‌‌‌‌‌‌‌ |bn+1–an+1| < ε. Корень уравнения есть среднее арифметическое последних полученных значений: ξ=(‌an+1+bn+1)/2 Лекция 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 1 и b0 = 0 ― явными многошаговыми. ― при r > 1 и b0 ≠ 0 ― неявными многошаговыми. Многошаговость нарушает однородность вычислительного процесса, используя для получения недостающей информации другие вычислительные схемы ( например, одношаговые). А) Метод Эйлера. Для решение Д.У.(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) приближённо заменяется прямолинейным отрезком, выходящим из точки М(хk;уk) с угловым коэффициентом f(хk;уk). В качестве приближения искомой интегральной кривой получаем ломаную линию с вершинами в точках М0(х0;у0), М1(х1;у1),…, Мn(хn;уn). Первое звено касается истинной интегральной кривой в точке М0(х0;у0). Метод Эйлера может быть применён к решению системы ОДУ и ДУ высших порядков. Последние должны быть предварительно приведены к системе ОДУ первого порядка. Пусть задана система ОДУ первого порядка: (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го порядка (15) (14) Грубая оценка погрешности (двойной просчёт): (16) Где у(хi) – точное решение, у*i – приближённое решение с шагом h/2, yi – … с шагом h . Для оценки правильности выбора шага h используют равенство: (17) q должно равняться нескольким сотым, иначе h уменьшается. D). Метод Рунге–Кутта 3-го порядка   Многошаговые методы. (используют информацию о нескольких предыдущих точках) Д ) Алгоритм Адамса. Пусть дано дифференциальное уравнение: у′ = 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) называются интерполяционными. Для грубой оценки точности (двойной просчёт):