Файл: Численные методы.pdf

Численные методы.

1.Источники погрешностей. Абсолютная и относительная погрешность числа. Значащие и

верные цифры.

При решении различных задач на компьютере, невозможно получить абсолютно точное значение y*, оно всегда содержит некую погрешность. Это следует из ограничения разрядности компьютера.

Причины погрешностей:

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

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

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

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

Пусть а – точное значение некоторой величины, а* - известное приближенное значение. Тогда абсолютная погрешность равна (a*)=|a-a*|. Однако по абсолютной погрешности нельзя сказать, большая погрешность или малая. Для этого существует относительная погрешность:

.

Значащими цифрами числа а* называют все цифры в его записи, начиная с первой ненулевой слева. ( . Значащую цифру числа а* называют верной, если

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

Количество верных значащих цифр числа тесно связано со значением его относительной погрешности. Если число а* содержит N верных значащих цифр, то справедливо неравенство

. Для того, чтобы число а* содержало N верных значащих цифр,

2. Погрешность вычисления функции одной переменной. Постановка задачи. Доказательство формулы.

Доказательство: Оценка вытекает из формулы конечных приращений Лагранжа:

Формулы для границ погрешностей функции f(x) одной переменной являются частным случаем при m=1:

.

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

Доказательство: Оценка вытекает из формулы конечных приращений Лагранжа:

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

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

Пусть между абсолютными погрешностями входных данных x и решения y установлено неравенство

Тогда величина называется абсолютным числом обусловленности. Если же установлено неравенство

Тогда величина называется относительным числом обусловленности. Чаще под числом обусловленности понимают относительное число обусловленности. Для плохо обусловленной задачи v>>1.

4. Особенности машинной арифметики. Понятия машинной бесконечности, машинного нуля, машинного эпсилон.

1) Системы счисления: принятый способ записи чисел состоит в представлении их упорядоченным набором цифр. В привычной нам десятичной системе счисления вещественное число х представляют последовательностью символов, которая начинается со знака (+ или -) и продолжается цепочкой десятичных цифр и , разделенных десятичной точкой

Здесь каждой позиции (разряду), которую занимает цифра относительно десятичной точки, отвечает определенная степень числа 10. Для хранения числа в памяти компьютера отводится поле стандартной длина (машинное слово), в котором число записывают в виде последовательности двоичных цифр. По форме представления, способу хранения и реализации арифметических операций существенно различаются на два типа используемых в компьютерах чисел: целые и вещественные.

а) представление целых чисел. Целое число n представляют в виде

, где L – некоторое стандартное для компьютера целое число, - двоичные цифры. Всего для хранения числа n отводят s=L+2 разрядов (один из них для хранения знака). Максимальное число, представимое в компьютере есть . Операции сложения, вычитания и умножения над целыми числами реализованы так, что если результат не превышает по модулю число , то он получается точным.

б) представление вещественных чисел. В современных компьютерах для вещественных чисел принята форма представления с плавающей точкой, когда каждое число представляют в виде

Здесь γ – двоичные цифры. Как правило, число x нормализуется так, чтобы , и поэтому в памяти компьютера хранятся только значащие цифры соответственного нормализованного числа. Число называют мантиссой числа х. В представлении (1) p –

целое число, называемое двоичным порядком. целое число, называемое двоичным порядком.

.

представления). Величина играет в вычислениях на компьютере фундаментальную роль; ее называют относительной точностью компьютера, или машинным эпсилоном.

Погрешность арифметических операций над числами с плавающей точкой равна

, где вместо может быть любая другая операция.

5. Решение нелинейных уравнений. Постановка задачи, основные этапы решения. Скорость сходимости итерационного метода. Интервал неопределенности корня.

Корнем (или решением) уравнения f(x)=0 называется значение , при котором f( )=0.

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

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

Основные этапы решения

Решение задачи отыскания корней нелинейного уравнения осуществляется в два этапа. Первый этап называют этапом локализации корней, второй – этапом итерационного уточнения корней.

Локализация корней. Отрезок [a,b], содержащий только один корень уравнения, называют отрезком локализации корня . Цель этапа локализации считается достигнутой, если для каждого из подлежащих определению корней удалось указать отрезок локализации (его длину стараются по возможности сделать минимальной). Но прежде чем приступать к локализации стоит провести предварительное исследование, имеется ли решение уравнения, сколько их и как они расположены на числовой оси.

Теорема: пусть функция f непрерывна на отрезке [a,b] и принимает на его концах значения разных знаков, т.е. f(a)*f(b)<0. Тогда отрезок [a,b] содержит по крайней мере один корень уравнения f(x)=0.

Итерационное уточнение корней. На этом этапе для вычисления каждого из корней с точностью ε>0 используют тот или иной итерационный метод, позволяющий построить

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

Скорость сходимости – одна из важнейших характеристик итерационных методов. Говорят, что метод сходится со скоростью геометрической прогрессии, знаменатель которой 0<q<1, если для всех n справедлива следующая оценка:

Пусть одношаговый итерационный метод обладает следующим свойством: существует σ-

окрестность корня такая, что если приближение принадлежит этой окрестности, то справедлива оценка:

Где C>0 и - постоянные. В этом случае р называют порядком сходимости метода.

Лемма 1. Пусть одношаговый итерационный метод обладает линейной скоростью сходимости в некоторой σ-окрестности корня . Тогда при любом выборе начального

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

Лемма 2. Пусть одношаговый итерационный метод в некоторой σ-окрестности корня