Лекции.Орг


Поиск:




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




Погрешность математической модели.

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

 

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

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

 

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

 

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

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

Есть случайные и систематические источники погрешности округления.

Случайные источники обычно компенсируют друг друга.

Например:

Знаки случайны и компенсируют друг друга при большом n.

Систематические источники вызывают накопление погрешности округления. Они являются дефектом структуры вычислений (алгоритма).

 

В машинной арифметике законы коммутативности ( переместительный ) и дистрибутивности ( распределительный ) не всегда соблюдаются.

Рекомендации для снижения ошибок округления:

  1. При сложении и вычитании последовательности чисел действия необходимо начинать с наименьших по абсолютной величине значений.
  2. Следует избегать вычитания двух близких чисел, преобразуя выражения.
  3. Количество арифметических действий для решения задачи нужно сводить к минимуму.
  4. Для уменьшения ошибки округления расчеты следует проводить с повышенной разрядностью (doubleprecisionв Pascal).

При выборе численного метода решения задачи необходимо учитывать следующее:

1. Погрешность метода должна быть на порядок меньше неустранимой погрешности. Увеличение погрешности метода снижает точность, уменьшение – увеличивает время решения задачи.

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

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

1. Решить задачу различными численными методами и результаты сравнить.

2. Незначительно изменить исходные данные и повторно решить задачу. Результаты сравнить. Если они различаются сильно, задача или метод ее решения являются неустойчивым – выбрать другой.

 

 

3.) Пусть в результате решения задачи по исходному значению величины x находится значение искомой величины y. Если исходная величина имеет абсолютную погрешность D x, то решение имеет погрешность D y. Задача называется устойчивой по исходному параметру x, если решение y непрерывно от него зависит, т. е. малое приращение исходной величины D x приводит к малому приращению искомой величины D y. (малые погрешности в исходной величине приводят к малым погрешностям в результате расчетов.)
Отсутствие устойчивости означает, что даже незначительные погрешности в исходных данных приводят к большим погрешностям в решении или к неверному результату.

 

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

 

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

 

Сходимость численного метода- близость получаемого численного решения задачи к истинному решению.

 

Сходимость итерационного процесса - этот процесс состоит в том, что для решения некоторой задачи и нахождения искомого значения определяемого параметра (например, корня нелинейного уравнения) строится метод последовательных приближений. В результате многократного повторения этого процесса (или итераций) получаем последовательность значений x1, x2,…, xn,… Говорят, что эта последовательность сходится к точному решению x = a, если при неограниченном возрастании числа итераций предел этой

последовательности существует и равен a: - сходящийся численный метод.

4.)

 

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

Методы решения уравнений:

  • Прямые (формула Виета для квадратного уравнения и Кардано для кубического и другие)
  • Итерационные – для решения любого уравнения

Общая постановка задачи: Найти действительные корни уравнения , где - алгебраическая или трансцендентная функция.

Численное решение уравнения проводится в два этапа:

1 этап. Отделение корней уравнения.

2 этап. Уточнение интересующих корней с заданной точностью ε.

 

Отделение корней – это определение их наличия, количества и нахождение для каждого из них достаточно малого отрезка [a,b], которому он принадлежит.

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

Задача отделения вещественных корней решается аналитическими и графическими методами.

Аналитические методы основаны на функциональном анализе.

Для алгебраического многочлена n-ой степени (полинома) с действительными коэффициентами вида

Pn(x) = an x n + an-1xn-1 +...+a1x+ a0 = 0, (an >0)

верхняя граница положительных действительных корней определяется по формуле Лагранжа (Маклорена):

,

где: k ³ 1 – номер первого из отрицательных коэффициентов полинома;

B – максимальный по модулю отрицательный коэффициент.

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

Если для этого уравнения по формуле Лагранжа верхняя граница равна R1, то

=

Тогда все положительные корни многочлена лежат в интервале

≤x+.

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

и .

≤x = = .

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

Отделить корни уравнения, используя аналитический метод:

Методом Лагранжа определим границы положительных и отрицательных корней многочлена.

3x8 – 5x7 – 6x3 – x – 9 = 0

k = 1 B = |– 9| an = 3

= 4

9x8 + x7 + 6x5 + 5x – 3 = 0

 
 

k = 8 B = 3 an = 9

 

Отсюда границы положительных корней 0,5 ≤ x+ ≤ 4

3x8 + 5x7 + 6x3 + x – 9 = 0

=

9x8 – x7 – 6x5 – 5x – 3 = 0

k = 1 B = 6 an = 9

 
 

Следовательно, границы отрицательных корней –2 ≤ x≤ –0,6

 

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

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

 

Графически корни можно отделить 2-мя способами:

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

  На графике 3 корня. Первый корень x * Î [a,b]
b x2* x3*
x
x1*
a
y=f(x)
y

Отделение корней на графике f(x).

y=f(x)


  1. Преобразовать f(x)=0 к виду j(x) = y(x), где j(x) и y(x) – элементарные функции, и определить абсциссу пересечений графиков этих функций.

       
   
  На графике 2 корня. Первый корень x 1* Î [a,b]
 
 


Отделение корней по графикам функций j(x) и y(x).

 


Схема алгоритма отделения корней.

5.)

Уточнение корня – это вычисление интересующего корня с заданной точностью e.

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

Метод дихотомии (половинного деления, бисекций) - (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка [a; b], где находится корень.

 

Алгоритм метода.

  1. Вычислить координату середины отрезка [a,b] x = (a+b)/2 и значение ¦(x) в этой точке.
  2. Уменьшить отрезок, отбросив ту его половину, на которой корня нет.

Если знак функции в начале отрезка и в его середине одинаков, то корень находится на второй половине, первую половину можно отбросить, переместив начало отрезка в его середину:

если ¦(a) ·¦(x)>0 => x*Î [x,b] => a=x, иначе x*Î [a, x] => b=x

  1. Проверить условие завершения вычислений: длина отрезка не превышает заданную точность и значение функции близко к 0 с заданной точностью:

b-a ≤ ε ∩ |¦(x)| ≤ ε.

Если условие достигнуто, расчет завершен, иначе повторить алгоритм сначала.

 

 

 
 

 


Геометрическая интерпретация.

 

 

 

 


b=x

 


 


Схема алгоритма метода бисекций (дихотомии)

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

 
 

 


Геометрическая интерпретация метода Ньютона.

Уточнение корня – это вычисление интересующего корня с заданной точностью e.

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

 

На отрезке существования корня выбирается начальное приближение x0. К кривой f(x) в точке А с координатами (x0, f(x0)) проводится касательная. Абсцисса x1 точки пересечения этой касательной с осью ОХ является новым приближением корня.

Из рисунка следует, что x1 = x0 − CB

Из ∆ABC: CD= . Но .

Следовательно,

Аналогично, для i-го приближения можно записать формулу итерационного процесса метода Ньютона:

, где x0 Î [a;b]. (3.13)

Условие окончания расчета: , (3.14)

где −корректирующее приращение или поправка.

Условие сходимости итерационного процесса:

(3.15)

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

, x0Î[a;b]. (3.16)

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

 

 

 

Геометрическая иллюстрация выбора начального приближения: график f(x) вогнутый, , тогда x0=b, т.к. f(b)>0.

Если же выбрать x0=a, то итерационный процесс будет сходиться медленнее или даже расходиться (см. касательную для x0=a).

 

 

Геометрическая иллюстрация выбора начального приближения: график

f(x) выпуклый, f ’’(x)<0, тогда x0 =a, т.к. f(a)<0.


Схема алгоритма метода Ньютона:

 

7.)

Метод хорд (секущих).

Этот метод применяется при решении уравнений вида , если корень уравнения отделён, т.е. и выполняются условия:

1) (функция принимает значения разных знаков на концах отрезка );

2) производная сохраняет знак на отрезке (функция либо возрастает, либо убывает на отрезке ).

Первое приближение корня находится по формуле: .

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

Тогда второе приближение вычисляется по формуле:

, если или , если .

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

Геометрическая интерпретация нахождение решения методом хорд:

При решении уравнения методом хорд поводится прямая соединяющая концы отрезка [a,b]. Из двух точек А и В выбирается х0. Находится точка пересечения хорды с осью OX. Определяется значение функции в точке пересечения и из найденной точки проводится новая хорда. Этот процесс повторяется до получения необходимой точности.

Формула для n-го приближения имеет вид(х0=а, xn-1=b,xn=x):

В методе хорд условием окончания итераций является:

- условие близости двух последовательных приближений: ;

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

Описание алгоритма метода хорд
Шаг 1. Ввод a,b,ε.
Шаг 2. X:=a-f(a)×(b-a)/(f(b)-f(a)).
Шаг 3. Если dF2(b)×F(b)<0, то a:=x;
Если dF2(a)×F(a)<0, то b:=x;
Шаг 4. Пересчитать X по формуле шага 2.
Шаг 5. Выполнять шаг 3, пока abs(b-a)<=eps.
Шаг 4.Вывод результата – x.
Опишем назначение переменных и функций, используемых в процедуре Hord
dF2 – значение второй производной в точке Х
F – значение функции в точке Х
Х0 – начальное значение Х
А – левая граница
В – правая граница
Е – точность вычислений
Fa – значение функции в точке А
Fb - значение функции в точке В
Представим в виде структурной схемы.

 

 

Блок схема алгоритма метода хорд:

 

 

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

xi=φ(xi-1), i=1,2,… где i − номер итерации.- последовательное вычисление значений xi по формуле называется итерационным процессом метода простых итераций, а сама формула - формулой итерационного процесса метода.

 

Алгоритм решения нелинейного уравнения методом
простых итераций:

 

 

 


Если , то итерационный процесс сходящийся.

Условие сходимости

Точное решение x* получить невозможно, так как требуется бесконечный итерационный процесс.

Можно получить приближенное решение, прервав итерационный xi=φ(xi-1) при достижении условия

,

где ε - заданная точность; i - номер последней итерации.

В большинстве случаев условие завершения итерационного процесса обеспечивает близость значения xi к точному решению:

Геометрическая иллюстрация метода простых итераций:

1) Итерационный процесс для случая 0< <1 xÎ[a,b].:

 
 

 

 


2) Итерационный процесс для случая -1< <1 xÎ[a,b].:

 

 

3)Итерационный процесс для случая >1 xÎ[a,b].

 


4)Итерационный процесс для случая £ - 1 xÎ[a,b].

 

 


9.) Методы решения систем линейных алгебраических уравнений:

Прямые(конечные) методы решения СЛАУ: (позволяют найти решение за определенное число операций.)
Метод Крамера
Метод обратной матрицы
Метод Гаусса

Итерационные методы решения линейных алгебраических систем: (основанны на использовании повторяющегося (циклического) процесса и позволяющие получить решение в результате последовательных приближений.)
Метод простой итерации или метод Якоби
Метод Гаусса – Зейделя

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

Требуется найти решение системы m линейных уравнений, которая записывается в общем виде как

,

Эту систему уравнений можно записать также в матричном виде:

,

где , , .

A – матрица системы, – вектор правых частей, – вектор неизвестных.

При известных A и требуется найти такие , при подстановке которых в систему уравнений она превращается в тождество.

Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество.

Система называется обусловленной (не вырожденной, не особенной), если определитель системы DA ¹ 0, и тогда система имеет единственное решение.

Система называется не обусловленной (вырожденной, особенной), если DA = 0, и тогда система не имеет решений или имеет бесконечное множество решений.

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





Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 663 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Велико ли, мало ли дело, его надо делать. © Неизвестно
==> читать все изречения...

998 - | 762 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.