Xreferat.com » Рефераты по математике » Численные методы

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

src="http://xreferat.ru/image/54/1306472768_18.gif" alt="" width="32" height="2" align="LEFT" /> (k) (k-1) (k-1)

fi = fi - aikyk ; k=1,m . (16)


Коефіціенти cij і праві частини yi ; i=1,m ; j=i+1,m зберігаються у пам’яті ЕОМ і використовуються при здійсненні зворотнього ходу за формулами (10).

Основним обмеженням методу є припущення, що усі елементи , на які здійснюється ділення, відрізняються від нуля. Число називається провідним елементом на К-му кроці вилучення. Навіть, якщо деякий провідний елемент не дорівнює нулеві, а просто є близьким до нуля, в процесі обчислень може мати місце нагромадження похибок. Вихід з цієї ситуації полягає в тому, шо як провідний елемент вибирається не , а інше число ( тобто на К-му кроці вилучається не xk, а інша змінна xj , ) . Така стратегія вибору провідних елементів здійснюється в методі Гаусса з вибором головного елементу, який буде розглянуто пізніш.

А тепер підрахуємо число арифметичних дій, що необхідні для розв’язання системи за допомогою методу Гаусса. Оскільки виконання операцій множення і ділення на ЕОМ потребує набагато більше часу, ніж виконання додавання і віднімання, обмежимось підрахуванням числа множень і ділень.

1.Обчислення коефіцієнтів за формулами (13) потребує:

(m-k)=1+2+...+(m-1)= ділень .

2.Обчислення усіх коефіцієнтів за формулами (14) потребує

множень (тут ми використовуємо легко перевіряєму за індукцією рівність ).

Таким чином, обчислення ненульових елементів трикутної матриці С потребує

операцій множення і ділення.

3.Обчислення правих частин yk за формулами (15) потребує m

ділень, а відшукання за формулами (16)

множень. Разом, обчислення правих частин перетвореної системи (8) потребує

дій множення і ділення.

Усього для реалізації прямого ходу методу Гаусса необхідно виконати

дій.

4.Для реалізації зворотнього ходу методу Гаусса за формулами (10) необхідно

множень.

Всього, для реалізації методу Гаусса необхідно виконати

дій множення і ділення, причому основний час витрачається на прямий хід. Для великих m число дій множення і ділення у методі Гаусса близьке до За витратами часу та необхідній машинній пам’яті метод Гаусса придатний для розв’язання систем рівнянь (2) загального вигляду з кількістю змінних m порядку 100.


ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ .


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

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

Простейшая идея численного дифференцирования состоит в том, что функция заменяется интерполяционным многочленом (Лагранжа, Ньютона) и производная функции приближенного заменяется соответствующей производной интерполяционного многочлена

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

Будем предполагать, что функция задана в равностоящих узлах


Ее значения и значения производных в узлах будем обозначать

Пусть функция задана в двух точках и ее значения

Посстроим интерполяционный многочлен первой степени


Производная равна

Производную функцию в точке приближенно заменяем производной интерполяционного многочлена

(1)

Величина называется первой разностной производной.

Пусть задана в трех точках

Интерполяционный многочлен Ньютона второй степени имеет вид

Берем производную

В точке она равна

Получаем приближенную формулу

(2)

Величина называется центральной разностной производной.

Наконец, если взять вторую производную

получаем приближенную формулу.

(3)

Величина называется второй разностной производной.

Формулы (1)-(3) называются формулами численного дифференцирования.

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

В дальнейшем нам понадобится следующая лемма.

Лемма 1. Пусть произвольные точки, Тогда существует такая точка что

Доказательство. Очевидно неравенство

По теореме Больцано-Коши о промежуточных значениях непрерывной функции на замкнутом отрезке она принимает все значения между и Значит существует такая точка что выполняет указанное в лемме равенство.

Погрешности формул численного дифференцирования дает следующая лемма.

Лемма 2.

1.Предположим, что Тогда существует такая точка , что

(4)

  1. Если то существует такая точка , что

(5)

  1. Когда то существует такая, что

(6) Доказательство. По формуле Тейлора

откуда следует (4).

Если то по формуле Тейлора

(7)

где

Подставим (7) в Получаем

Заменяя в соответствии с леммою 1

получаем

Откуда и следует (6).

Равенство (5) доказывается аналогично ( доказательство провести самостоятельно).

Формулы (4)-(6) называются формулами численного дифференцирования с остаточными членами.

Погрешности формул (1)-(3) оцениваются с помощью следующих неравенств, которые вытекают из соотношений (4)-(6):

Говорят, что погрешность формулы (1) имеет первый порядок относительно (или порядка ), а погрешность формул (2) и (3) имеет второй порядок относительно (или порядка ). Также говорят, что формула численного дифференцирования (1) первого порядка точности (относительно ), а формулы (2) и (3) имеют второй порядок точности.

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

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

(8)

Пусть в некоторой окрестности точки производные, через которые выражаются остаточные члены в формулах (5), (6), непрерывны и удовлетворяют неравенствам

(9)

где - некоторые числа. Тогда полная погрешность формул (2), (3) (без учета погрешностей округления) в соответствии с (5), (6), (8), (9)не превосходит соответственно величин

Минимизация по этих величин приводит к следующим значениям

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: