Восемь лекций по численным методам Конспект лекций по курсу icon

Восемь лекций по численным методам Конспект лекций по курсу



Смотрите также:
  1   2   3   4   5   6   7   8


Министерство образования и науки Украины

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

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

Кафедра компьютерных систем мониторинга


В. Н. Беловодский

Восемь лекций по численным методам

(Конспект лекций по курсу

«Численные методы в информатике»

для студентов специальности

7.080407 «Компьютерный эколого-экономический мониторинг»)


Рассмотрено на заседании кафедры КСМ протокол № 1 от 30 августа 2005г.

Утверждено на учебно-методическом совете ДонНТУ №4956


Донецк-2005

УДК 519.95

Беловодский В.Н. Восемь лекций по численным методам: Конспект лекций по курсу «Численные методы в информатике» для студентов специальности 7.080407 «Компьютерный эколого-экономический мониторинг»). – Донецк: ДонНТУ, 2005. - 101 с.


Содержит минимальные теоретические сведения, рассчитанные на 32 лекционных часа, излагаемые студентам специальности КЭМ по курсу «Численные методы в информатике». Каждая лекция (3 - 5 аудиторных часов) посвящена одному из разделов курса, приводятся варианты индивидуальных заданий по каждому из них.


Содержание

Введение

5

Лекция 1.Элементы теории погрешностей

6

    1. Типы и источники погрешностей

6

    1. Абсолютные и относительные погрешности приближённых чисел

6

    1. Погрешности выполнения арифметических операций

7

    1. Погрешность вычисления функции

10

    1. Запись приближённых чисел

12

    1. Правила действий над приближёнными числами

13

    1. Погрешности при машинном представлении чисел

14

    1. Задание, варианты

16

Лекция 2.Интерполяция функций

17

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

17

    1. Алгебраическая интерполяция, существование и единственность интерполяционного многочлена

17

    1. Интерполяционный многочлен Лагранжа

18

    1. Конечные и разделенные разности

19

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

21

    1. Сравнительный анализ интерполяционных многочленов

22

    1. Погрешности интерполяционных формул

22

    1. Интерполяционные формулы для равноотстоящих узлов

24

    1. Сплайн интерполяция

27

    1. Задание, варианты

30

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

31

    1. Предварительные замечания

31

    1. Точные методы решения

32

    1. Приближенные методы решения

35

    1. Сходимость и погрешность приближённых методов




37

    1. Приведение системы Ax=b к нормальному виду

41

    1. Задание, варианты

44

Лекция 4.Решение нелинейных уравнений

46

    1. Предварительные замечания

46

    1. Методы, основанные на алгебраическом интерполировании

48

    1. Метод последовательных приближений

51

    1. Задание, варианты

52

Лекция 5.Решение систем нелинейных уравнений

55

    1. Метод итераций

55

    1. Метод Ньютона

59

    1. Сравнительный анализ методов

60

    1. Задание, варианты

60

Лекция 6.Приближенное вычисление определенных интегралов

65

    1. Вступительные замечания

65

    1. Формулы Ньютона-Котеса

65

    1. Простейшие квадратурные правила

68

    1. Погрешности квадратурных формул

71

    1. Понятие о методах Монте-Карло

73

    1. Задание, варианты

74

Лекция 7.Методы решения обыкновенных дифференциальных уравнений

78

    1. Вступительные замечания

78

    1. Аналитические методы решения

78

    1. Численные методы, правило Рунге

81

    1. Задание, варианты

87

Лекция 8.Основы спектрального анализа

90

8.1. Элементы общей теории

90

8.2. Комплексная форма рядов Фурье

93

8.3. Дискретная форма рядов Фурье

94

8.4. Задание, варианты

95

Дополнительная литература

101

Введение


Данное учебное пособие представляет собой конспект лекций по курсу «Численные методы в информатике», который читается студентам специальности 7.080407 «Компьютерный эколого-экономический мониторинг» и является, по существу, введением в соответствующий раздел математики. Структурно состоит из восьми лекций, каждая из которых посвящена одному из разделов курса, и содержит базовые теоретические сведения, призванные создать фундамент, необходимый для дальнейшего самостоятельного изучения данного предмета.

При формировании тематики курса учитывалось содержание известных пакетов прикладных программ. Из-за незначительного времени, выделяемого на данный курс (32 лекционных часа) в него не удалось включить ряд важных разделов. Это в первую очередь относится к вычислительным методам линейной алгебры и приближенным методам решения уравнений в частных производных. Отчасти их отсутствие компенсируется кратким обзором приближенных методов в курсе «Линейная алгебра и аналитическая геометрия», а разностные схемы включены в курс «Краевые задачи математической физики».

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


^ Лекция 1.Элементы теории погрешностей


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


    1. ^ .Типы и источники погрешносте


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

Поясним это на примере.

Предположим, что вычисление значения sinx решено проводить по формуле .

Тогда неточность в задании значения x , если она есть, образует неустранимую погрешность. Величина sinx-f(x) представит собой погрешность аппроксимации. А проводимые в процессе вычислений округления, обусловят вычислительную погрешность.

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


1.2.Абсолютные и относительные погрешности приближённых чисел


Эти понятия относятся к числу базовых в теории погрешностей.

Обозначим через точное значение некоторой величины, через x ,- его приближенное значение. Тогда разность называется погрешностью приближённого числа x. При действиях с приближёнными числами обычно известно, что абсолютная величина погрешности не превосходит некоторой величины , т.е.





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

Отношение



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



называется относительной погрешностью числа x. Очевидно, что и .

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

,

то .


^ 1.3. Погрешности выполнения арифметических операций


Установим характер развития погрешностей при выполнении арифметических операций. Обозначим , где - один из символов ± , ∙, ÷ . Будем считать известными погрешности операндов ∆(x), ∆(y), δ(x), δ(y) и обозначим через ,,их точные значения.

Сложение. В данном случае , где - числа одного знака. Тогда справедливы следующие оценки


.

Таким образом, имеем


, (1.1)


т.е. абсолютная погрешность суммы двух приближённых чисел равно сумме абсолютных погрешностей слагаемых.

Полученный результат очевидным образом обобщается и на произвольное число слагаемых.

Далее, так как


,


то

. (1.2)

Вычитание. В данном случае , где значения - числа одного знака. Также, как и в случае сложения, здесь




т.е.


, (1.3)


что совпадает с (1.1).

Таким же образом,

,


и

, (1.4)


что совпадает с (1.2).

Анализ выражений (1.3), (1.4) показывает, что при вычитании близких чисел , т.е. при z → 0, погрешность ∆(z) может превышать результат, а величина δ(z)→ ∞. Поэтому при вычислениях необходимо избегать вычитания близких чисел.


Умножение. В данном случае . Тогда




Далее, учитывая


,

имеем


.

Таким образом

, (1.5)

а

. (1.6)


Отметим, если или ‹‹ 1, то

. (1.61)


Деление. В данном случае . Тогда




Учитывая, что , имеем


.

Таким образом

, (1.7)

Здесь, естественно, предполагается, что .

Далее, так как


,

то


(1.8)

Если ‹‹ 1, то

,

что совпадает с (1.61).

Сведём в таблицу полученные результаты.


Таблица 1.1. Погрешности выполнения арифметических операций




Операция





Примечания


1.


z=x+ y










2.


z=x - y










3.


z=x∙y






,

если или

‹‹ 1


4.








,

если

‹‹ 1




    1. .Погрешность вычисления функции


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

Оценим абсолютную величину погрешности функции. С этой целью, используя теорему Лагранжа, получим


(1.9)


где .


Используя, далее свойство модуля суммы, имеем


.

И, наконец, исключая зависимость оценки от неизвестных величин , получим

,

где , ,

.

Обозначим

.


Если в начале преобразований (1.9) к исходному выражению прибавить , то в результате аналогичных действий получим вторую оценку


,

где

,


где

, .


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

.


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


. (1.10)


Действительно, в силу , , очевидно и .

В этом случае из (1.10) для следует выражение

(1.11)


Аналогичным образом, для функции нескольких переменных , получим



и

,

где

.


^ 1.5.Запись приближённых чисел


Приближённые числа принято записывать, указывая лишь верные значащие цифры. Рассмотрим - число, представленное виде десятичной, а вообще говоря, n-ичной дроби. Его цифры, начиная с первой отличной от нуля слева, называются значащими. Например, в числе 0.010230 пять значащих цифр, это - 1, 0, 2, 3, 0. Значащая цифра называется верной, если модуль погрешности числа не превышает единицу разряда, соответствующей этой цифре. Так как погрешность числа, как правило, неизвестна, то при определении верных знаков используют абсолютную погрешность. Так, пусть, например, погрешность числа x = 12.3405 равна 0.001. Тогда верными значащими цифрами являются 1, 2, 3, 4, 0.

Для записи числа с верными значащими цифрами используют как n- ичную, так и показательную формы. Пусть, например, исходное приближённое число x = 1203.045, а =0.03. Тогда верными являются цифры 1, 2, 0, 3, 0 и возможны записи: x = 1203.0 или 120.30∙10 или 0.12030∙104 и т.д.

Заметим, что запись без последнего справа нуля, например, 120.3∙10 неверна. Если же , то верными являются цифры 1, 2, 0 и число следует записать так: x=120∙10 или 0.120∙104 , т. е. сохраняя его в записи ровно три значащие цифры. Запись x=1200 или x=0.12 ∙104 будет неверна.

Запись чисел, содержащая лишь верные значащие цифры, обладает определённым достоинством, т.к. дает возможность составлять суждения о величине абсолютной и относительной погрешности. Действительно, пусть запись x=0.012 содержит лишь верные знаки. Тогда, при отсутствии иной информации, следует считать , отсюда .


^ 1.6.Правила действий над приближёнными числами


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


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





страница1/8
Дата конвертации23.10.2013
Размер0,95 Mb.
ТипКонспект
  1   2   3   4   5   6   7   8
Разместите кнопку на своём сайте или блоге:
rud.exdat.com


База данных защищена авторским правом ©exdat 2000-2012
При копировании материала укажите ссылку
обратиться к администрации
Документы