Основы численных методов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Вычислительная математика. Численные методы. Этапы решения задач на ЭВМ

Если метод решения 4 задачи неизвестен, то можно попробовать упростить математическую модель.

Математика настолько проста, что обладает внутренней логикой. От того, что она логически проста эту цепочку можно логически правильно построить.

Если взять другую модель, то внутри модели модель не обладает внутренней логикой.

Решение задач.

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

2. построение математической модели: описываются основные понятия, отбрасываются те или иные второстепенные данные; переформулировка задачи; выбор методов решения.

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

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

5. анализ или интерпретация результатов. На этом этапе происходит осмысление полученных результатов, сопоставление их с рез-ми контрольного просчета, а также с данными, полученными экспериментальным путем.

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

Погрешности не могут умножаться друг на друга, они имеют тенденцию увеличиваться или уменьшаться (пример с яблоком и двумя червями). На различных этапах решения задачи вносятся те или иные погрешности, причинами которых могут быть: 1. введение новых объектов, понятий; отбрасывание несущественных деталей; математическое описание исходной задачи является неточным (в частности за счет неточно заданных исходных данных).

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

3. погрешности, привносимые при выполнении арифметических действий и при округлении окончательного и промежуточного результата.

Погрешности бывают:

1. неустранимые (связанные с моделью);

2. погрешности метода;

3. вычислительные погрешности;

4. ошибки, неправильные действия.

Полная погрешность задачи. Обоз-м через Т - точное решение задачи, Р - решение задачи в рамках математической модели; Р₁ - решение задачи, полученное при реализации численного метода в предположении отсутствия округления; Р₂ - решение задачи в практических вычислениях; ? - погрешность. ?=IТ-Р₂I=IТ-Р+Р-Р₁+Р₁-Р₂I?IТ-РI+IР-Р₁I+IР₁-Р₂I. Обозначим через ?₁=IТ-РI - неустранимую погрешность, ?₂=IР-Р₁I - погрешность метода, ?₃=IР₁-Р₂I - вычислительную погрешность. Тогда ???₁+ ?₂+?₃.

2. Округление чисел. Правило округления. Примеры

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

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

если первая (слева) отбрасываемая цифра меньше 5, то все сохраняемые цифры остаются без изменения;

если первая отбрасываемая цифра больше 5 или если она равна
5, но среди остальных отбрасываемых цифр есть ненулевые, то к
последней сохраняемой цифре прибавляется единица;

если первая отбрасываемая цифра равна 5 и все остальные отбрасываемые цифры являются нулями, то последняя сохраняемая цифра остается неизменной, если она четная, и увеличивается на единицу, если она нечетная.

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

Потребность замены цифр нулями для сохранения разрядов возникает при округлении целых чисел. Например, округляя число 56 998 до трех значащих цифр, получим в результате 57 000. Первый из трех нулей является значащим, остальные два сохраняют разрядность числа - это нули округления.

Для того чтобы по записи таких чисел можно было узнать, какой нуль значащий, а какой нет, их записывают в виде т ¦ 10^р, оставляя значащие нули в мантиссе т. Приведенное выше число следует представить как 570 * 10².

3. Приближенное решение нелинейных уравнений. Аналитический и геометрич. метод отделения корней

F(x)=0, y=F(x) определена и непр. На [a; b] ? є [a; b] F(?)=0.

Теорема 1: если непрерывная ф-я y=F(x) принимает зн-я разных знаков на концах [a; b] F(a)*F(b)<0, то внутри отрезка содержится по меньшей мере 1 корень уравнения, т.е. сущ. ? є [a; b] что F(?)=0 Следствие: если выполняется условие Т1, сущ. F' (x) сохраняющая знак внутри (0<|F' (x)| xє [a; b]), то сущ.-ет ?₀ є [a; b] что F(?₀)=0; Теорема2: Оценка погрешности приб корня: пусть ?-точное решение ??-приближенное реш-е F(x)=0 ?, ?? є [a; b], 0<M<=|F? (x)|, тогда справедливо ???=|?-??|<=(F(b)/M). Пример: F₁(x)=0 F₂(x)=0; F₁(?₁с волной)<=E1; F₂(?₂с волной)<=E2; E₁<<E₂не_следует ??₁с_волной << ??₂с_волной.

4. Приближенное решение нелинейных уравнений. Метод итерации. Достаточное условие сходимости

уравнение нелинейный аналитический сходимость

Постановка задачи. Дано нелинейное уравнение, где функция y=F(x) определена и непрерывно-дифференцируема для всех , причем функция меняет знак на концах этого отрезка, т.е. F(a) F(b)<0.

Найти приближенное решение данного уравнения F(x)=0 с точностью .

Приближенное решение и погрешность приближения находятся по следующей схеме:

- уравнение F(x)=0 приводится к виду , где функция удовлетворяет условиям: [a, b], дифференцируема на данном отрезке и ;

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

Приближенное решение и погрешность приближения :

, . Достаточное условие сходимости. Теорема: Пусть функция определена и дифференцируема на отрезке [a, b], причем все ее значения [a, b]. Тогда, если существует правильная дробь q такая, что (1) при a<x<b, то 1) процесс итерации (2) сходится независимо от начального значения ; 2) предельное значение является единственным корнем уравнения (3) на отрезке [a, b].

Док-во: Рассмотрим два последовательных приближения и . Отсюда . Применяя теорему Лагранжа, будем иметь: , где . Следовательно, на основании (1) получим: (4). Отсюда, давая значения n=1, 2, 3, …, последовательно выводим:

(5)

Рассмотрим ряд (6) для которого наши последовательные приближения являются (n+1) - ми частными суммами .

В силу неравенства (5) члены ряда (6) по абсолютной величине меньше соответствующих членов геометрической прогрессии со знаменателем q<1, поэтому ряд (6) сходится и притом абсолютно. Следовательно, существует , причем, очевидно, . Переходя к пределу в равенстве (2), в силу непрерывности функции получаем: (7). Т.о., есть корень уравнения (3). Другого корня Ур. (3) не имеет. Действительно, если (8), то из равенства (7) и (8) получим: и, следовательно, (9), где . Т.к. выражение в кв. скобке в равенстве (9) не равно нулю, то , т.е. - единственный. /ч.т.д.

5. Приближ реш систем лин ур. Постановка задачи. Метод итерации. Достаточное условие сходимости

Методы решения систем делятся на точные методы, позволяющие выч-ть корни системы (правило Крамера, метод Гаусса, метод главных элементов, м/д Халецкого и др.) и итерационные м/ды позволяющие находить корни с заданной точностью (м/д итерации, Зейделя (явные и неявные методы), м/д релаксации, …). Погрешности привносильные при этом итерац-ми методами как ошибка округления и погрешности метода. Метод Гаусса. Под названием «метод Гаусса» фигурирует группа методов, объединенных идеей последовательного исключения неизвестных. Наиболее популярным является метод, основанный на так называемой схеме единственного деления; этот метод имеет также и ряд модификаций. Кроме решения систем уравнений метод Гаусса весьма эффективен и для решения некоторых других задач, которые будут рассмотрены ниже.

Будем далее считать матрицу системы

(3.1) невырожденной. Суть метода Гаусса состоит в преобразовании системы (3.1) к равносильной ей системе с треугольной матрицей, из которой затем последовательно (обратным ходом) получаются значения всех неизвестных. Сам по себе метод Гаусса относится к точным методам. Это означает, что если точно выполнять все требуемые в нем действия, то будет получено точное решение, поскольку погрешность метода в данном случае равна нулю. Понятно, однако, что из-за вычислительных ошибок (включая ошибки округления, а также возможные ошибки исходных данных) этот идеал практически недостижим. Идея последовательного исключения неизвестных может быть реализована различными вычислительными схемами. Ниже рассматривается алгоритм, который получил название схемы единственного деления. Подвергнем систему (3.1) следующему преобразованию. Считая, что а₁₁ 0 (ведущий элемент), разделим на а₁₁ коэффициенты первого уравнения:

х₁ + ₁₂х₂ +… + _1nх_n = ₁. (3.2) Пользуясь уравнением (3.2), легко исключить неизвестное x₁ из остальных уравнений системы (для этого достаточно из каждого уравнения вычесть уравнение (3.2), предварительно умноженное на соответствующий коэффициент при x₁).Затем, оставив первое уравнение в покое, над остальными уравнениями системы совершим аналогичное преобразование: выберем из их числа уравнение с ведущим элементом и исключим с его помощью из остальных уравнений неизвестное х₂. Повторяя этот процесс, вместо системы (3.2) получим равносильную ей систему с треугольной матрицей:

(3.3).

Из системы (3.3) последовательно находят значения неизвестных х_n, х_n-1., x₁. Таким образом, процесс решения системы (3.1) по методу Гаусса распадается на два этапа. Первый этап, состоящий в последовательном исключении неизвестных, называют прямым ходом. Второй этап вычислений - нахождение значений неизвестных - принято называть обратным ходом.

Метод итерации. Пусть дана система n лин-ых алг-их ур-ий с n неизвестными.

(1)

i=0,1..n (2).

b=(b₁, b₂., b_n)^T, x=(x₁, x₂., x_n)^T, A*x=b (3).

Тогда вектор х наз решением системы (1), (2), (3), если в подстановке х_i, i=0,1,2..n, (1), (2), (3) приводят систему в тождество, а компоненты х_i - корни.

Если или то существует и при том единств. x=(x₁, x₂., x_n)^T, A*x=b.

Псть дана с.л.у. A*x=b (4), А={a_ij}, i, j=1,2..n. (5)

a_ii0, приведем сист к след виду: (6) , х = (7). ,, i<>j.

Решая сист (7) итер-м способом, для этого полагаем что х⁽⁰⁾= тогда подставляя в (7) получаем , к=0,1,2. т.е. получаем последовательность вект-в {x^(k)} и если эта последовательность сходится то существует и предел lim x^(k)=, =(₁, ₂., _n)^T, то получим lim x^(k)= lim x^(k) =. В этом случае (продолжение18) вектор явл реш сист (7), а следовательно и системы (3)

условие сходимости итер процесса. Теорема1: если для приведенной системы (7) выполнено хотя бы одно из условий (i=1..n) или (j=1..n), то итерационный процесс сходится к единств реш этой системы независимо от выбора начального приближения. Для системы A*x=b метод итерации сходится, если выполнено условие i=1..n (j=1..n). Теорема2: Процесс итерации для приведенной системы (7) сходится единств. ее решению, если какая-нибудь каноническая норма матрицы <1, , где s={m, l, k} где , , . Действительно, из итерационной схемы имеем

х^(р)= .

Поскольку , то при тогда , ,

, =, , , . - решение системы.

Размещено на Allbest.ru