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

↑

▷ Содержание

Стр 1 из 17Следующая ⇒

Факультет кибернетики

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

КУРС ЛЕКЦИЙ

по дисциплине

ВЫЧИСЛИТЕЛЬНАЯ

МАТЕМАТИКА

Направления

подготовки: - 654600 “Информатика и вычислительная техника”

                   - 654700 “Информационные системы”

Специальности: 2201 “Вычислительные машины, комплексы,

                                     системы и сети ” (ЭВМ)

                             2202 “Автоматизированные системы обработки

                                      информации и управления ” (АСУ)

Информационные системы в технике и

                                         технологиях ” (МЭИ)

ЛЕКЦИЯ 1

Приближенные числа.

«В численных расчетах всегда есть

                                        бездна ловушек…»      

                               Форсайт, Малькольм, Моулер.                 

1. Источники погрешностей результатов вычислений.

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

б) в процессе вычислений иррациональные величины: π, е,  и т.д. могут быть представлены лишь приближенно;

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

г) ограниченное число разрядов в ЭВМ и т.д.

При решении задач на ЭВМ пользуются те или иные вычислительные схемы.

Пример, «ловушки» при численных расчетах [Березин, Жидков, т 1 стр. 39]

Вычислить объем шара, заключенного между цилиндром радиуса R и взаимно перпендикулярными плоскостями. Радиус шара – r.

;

Рассмотрим три различных вычислительных схемы:

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

 = 1,4142135624…

1.  = 1,4 = ; ∆₁ = 0,014 /∆₁ / = 0,014

2.  = 1,4166 =   ∆₂ = -0,0024 /∆₂ / = 0,0024

второе значение более точное.

Результаты сведем в таблицу

		(3-2 )	99-70
			1

Имеем 6 ответов (от -0,1666 до +1), существенно отличающихся друг от друга. Причем вариант -  очевидно абсурден. Сразу не ясно, какой из оставшихся результатов ближе к верному.

Один программист сказал: «написать две хороших подпрограммы на порядок легче, чем решить, какая из них лучше»

[Малькольм, Форсайт, Моулер]

Необходимость оценивать результаты программ обусловила необходимость анализа погрешностей.

2. Абсолютная и относительная погрешности,

       Под ошибкой или погрешностью, ∆а приближенного числа, а понимают разность между точным числом и приближенным

∆а = А – а    (иногда: ∆а = а – А)

Абсолютная погрешность приближенного числа

∆ = ‌‌‌‌‌/∆а/    ∆ = /А-а/ 

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

∆ = ‌/А – а/ ≤ ∆а  (1)

Т.о.

   а – ∆а ≤ А ≤ а +∆а

Или

  А = а ± ∆а

       Пример: определить ∆а числа а = 3,14, заменяющего π.

Решение: 3,14 < π < 3,15

             /а – π/ < 0,01                                   т.о. ∆а = 0,01

Если учесть, что

3,14 < π < 3,142, то ∆а = 0,02

Нужно выбирать нижнюю грань числа ∆а, удовлетворяющего неравенству (1).

       Относительной погрешностью δ приближенного числа а называют отношение абсолютной погрешности ∆ к модулю точного числа А (А ≠0)

δ =                   (2)

т.е.  ∆ = /А/ • δ

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

δ ≤ δа т.е.  ≤ δа → ∆ = /А/ • δа

Сравнивая с (1) получаем: предельная абсолютная погрешность равная предельной относительной погрешности умноженной на модуль точного значения числа.

∆а = /А/ • δа             (3)

На практике считают (т.к. А ≈ а)

∆а = /а/ • δа              (4)

границы для точного числа А равны

а(1 – δа) и а(1 + δа)

т.о. А = а(1 ± δа)

3. Значащая цифра. Число верных знаков.

Примеры:

                                                                                незначащие цифры

значащие цифры

                                                                                                                                                       Т.о. для числа

а = α_m • 10^m +…+ α_m-n+1 – 10^{m-n +1} +…

(ли известно, что ∆ = /А – а/ ≤ 1/2 • 10^{m-n +1})

Пример: А = 35,97                    а = 36,00

В а верны три знака, т.к. /А – а/ = 0,03 < 1/2 • 0,1

следовательно, 0 • 10^-1  – верная значащая цифра.

4. Округление чисел.

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

1) если первая из отброшенных цифр < 5, то оставшиеся десятичные знаки сохраняются без изменения;

2) если первая из отброшенных цифр > 5, то к последней оставшейся цифре добавляется 1;

3) если первая из отброшенных цифр = 5 и среди отброшенных цифр есть ненулевые, то последняя оставшееся цифра увеличивается на 1;

4) если все отброшенные цифры (первая = 5) – нулевые, то последняя оставшееся цифра остается неизменной, если она четная, и увеличивается на 1, если она нечетная.

Рекомендации для практического применения:

1. Количество верных знаков числа отсчитывается от 1-ой значащей цифры числа до первой значащей цифры его абсолютной погрешности.                                    S = 20.7426;  ∆s = 0.0926                                                                                          верные знаки 2, 0, 7.                                                                                                            по определению 2, верные значащие цифры были бы 2,0, т.к. 0,09>

     1/2 • 0,1 = 0,05

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

Пример: Длина и ширина комнаты, измеренные с точностью до 1 см., равны

а = 5,43м; в = 3,82м. Оценить погрешность площади.

S = ав = 20,7426 м²

Решение: ∆а = 0,01м; ∆в = 0,01м

Smax = (a + 0.01)(в + 0,01) = 20,8952 м²            /Smax – S/ = 0,0926     

Smin = (a - 0.01)(в - 0,01) = 20,6502 м²              /Smin – S/ = 0,0924

∆S = 0,0926. Можно положить    ∆S = 0,1. Погрешность увеличивают при округлении. 

Приближенное значение S = 20,7 (или даже 21).

       5. Сложение и вычитание приближенных чисел.

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

если S = а₁+а₂+…±аn                                 

то ∆S = ∆а₁+∆а₂+…±∆аn

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

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

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

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

3. произвести сложение, учитывая все сохраненные знаки;

4. результат округлить на 1 знак

Пример: найти сумму приближенных чисел, каждое из которых имеет все верные значащие цифры:

0,348; 0,1834; 345,4; 235,2; 11,2; 11,75; 9,27; 0,0849; 0,0214; 0,000354.

Решение:1) выделяем числа наименьшей точности: 345,4; 235,2 (абсолютная погрешность может достигать 0,1).

2) округляем остальные числа до 0,01

получим

345,4	3) округляем результат до 0,1. По правилу четной цифры                      получаем:             S = 602,2
235,2
11,2
9,27
0,35
0,18
0,08
0,02
0,00
602,25

Абсолютная погрешность находится в (приближенно) как сумма абсолютных погрешностей исходных данных и погрешности округления

∆S = 0,10 + 0,05 = 0,15                ∆а = 0,2

Относительная погрешность δs суммы нескольких чисел одного и того же знака между наименьшей и наибольшей из относительных погрешностей слагаемых: min δак ≤ δs ≤ δак      (ак > 0, к = 1, 2, 3…, n)

Пример: оценить относительную погрешность суммы, найденной в предыдущем примере, и сравнить ее с относительными погрешностями слагаемых.

Решение: абсолютная погрешность (погрешность суммирования) ∆ равна 0,1. относительная погрешность δ = ∆/А:

Δ = 0,1/602,2 = 0,017 %

Относительные погрешности слагаемых: 0,0005/0,348 = 0,5/348 = 15 %

0,5/348 = 15 %; 0,5/1834 = 0,027 %; 0,5/3454 = 0,015 %

05/2352 = 0,022 %; 0,5/1175 = 0,043 %; 0,5/927 = 0,054 %

0,5/849 = 0,059 %; 0,5/214 = 0,24 %; 0,5/354 = 0,015 %

min δак = 0,015 %

max δак = 0,24 %

δs = 0,017 %

Наибольший вклад в сумму вносят слагаемые 345,4 (δ = 0,015 %) и 235,2 (δ = 0,022 %). δ заключена между этими значениями.

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

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

Пример: U = ; найти разность с тремя верными знаками.

 = 1,41774469

 = 1,41421356

U = 0,00353 = 3,53•10^–3 вычисления нужно вести с 6 знаками после запятой, т.е. 7 верных знаков.

Преобразуем U:

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

U =

ЛЕКЦИЯ 2

ЛЕКЦИЯ 3

ЛЕКЦИЯ 4

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

Рассмотрим систему линейных алгебраических уравнений

                (1)

Если все диагональные элементы , то систему (1) можно представить в приведенном виде

          (2)

где    

Введем обозначения

Тогда система (2) запишется в виде

                                       (3)

В качестве начального приближения  возьмем вектор b и подставим его в уравнение (3). Получим .Продолжая процесс, получим последовательности приближений:

- первое приближение

-второе приближение                (4)

.........

- (k+1)-ое приближение.

Если существует предел x последовательности векторов  то, переходя к пределу в равенстве  при , убеждаемся, что x является решением уравнения (3), т.е.

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

Теорема. Если какая-нибудь норма матрицы А меньше единицы: , то уравнение (3) имеет единственное решение x, к которому стремится последовательность итераций (4) при любом выборе начального приближения.

Под нормой матрицы понимают следующие выражения:

(m – норма - максимальное значение суммы модулей элементов строки)

  (l – норма - максимальное значение суммы модулей элементов столбца)

     (k - норма)

Пример: для матрицы                         

В расчетах полагают . Погрешности приближенного решения уравнения (3) на k-м шаге оценивают неравенством

 ,                  (5)

где - норма вектора X

      m-норма или кубическая норма

                             l-норма или октаэдрическая норма

                             k-норма или сферическая норма.

Из неравенства (5) можно получить оценку числа итераций k, необходимых для обеспечения заданной точности e.

Отклонение приближения  от решения x по норме не будет превышать e, если

           (6)

Для вывода (6) достаточно рассмотреть равенства:

;   ; ;

;

; и т.д.

Далее .

И, учитывая, что , т.к. норма .

В неравенствах (5) и (6) используются согласованные нормы для матриц и векторов, т.е. m и l-нормы.

Неравенство (6) дает завышенную оценку числа итераций k. Из (6) можно получить удобное условие, позволяющее принять приближение  в качестве решения с точностью e.

                              (7)

Пример: Найти решение системы уравнений

методом итераций с точностью 10^-2.

Решение: Приведем систему к виду (2)

Запишем последовательность итераций

                (8)

Для приведенной матрицы  достаточное условие сходимости выполняется по m-норме:

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

Число итераций для достижения заданной точности  определяем из неравенства (6) , которое запишем так:

, действительно: .

;  т.к. то ; .

Вычислим теперь три последовательных приближения по формулам (8) и оценим погрешность каждого результата, используя неравенство (6) в виде:

.  

Первое приближение:

Следовательно, дает значение корня ξ с погрешностью, не превышающей величины .

Далее последовательно находим:

;

.

Третья итерация:

;

.

Заданная точность достигается за 5 шагов. Точное решение .

ЛЕКЦИЯ 5

Основные понятия алгебры матриц и теории линейных векторных пространств.

1. Обратная матрица

Решение системы линейных уравнений

                                                (1)

находится как

                                       (2)

где А^-1-матрица, обратная к А

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

         (3)

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

Теорема: Всякая неособенная матрица имеет обратную матрицу.

Доказательство:Пусть дана неособенная матрица А

Определитель или детерминант квадратной матрицы А

(4)

 где сумма (4) распространена на всевозможные постановки (α₁,α₂,…α_n) элементов 1,2,3…n и, следовательно, содержит n! Слагаемых, причем n=0, если перестановка четная и n=1, если перестановка нечетная.

Перестановка называется четной, если четно число встречающихся в ней инверсий (Инверсия перестановки: когда α_i<α_j, при i >j)

Составим для матрицы А присоединенную матрицу

Где А_ij – алгебраическое дополнение (миноры со знаками) соответствующих элементов a_ij(i,j=1,2,3…n)

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

Обратная матрица А^*=А^-1 равна , где Δ – определитель

Для данной матрицы А ее обратная матрица А^-1  (если она существует) – единственная.

Теорема:

Особенная обратная матрица обратной не имеет.

Доказательство:

Если А-особенная матрица, то det A=0,

Отсюда следует, что

0=1

Теорема доказана.

Пример:

Для матрицы А найти обратную

Решение:

Составляем присоединенную матрицу:

Свойства обратной матрицы:

1. Определитель обратной матрицы равен обратной величине определителя исходной матрицы

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

3. Транспонированная обратная матрица равна обратной ей транспонированной данной матрицы

2. Ранг матрицы

Определение:

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

Матрица А имеет ранг r, если:

1. Найдется, по меньшей мере, один ее минор второго порядка, отличный от нуля.
2. Все миноры матрицы А порядка 2+1 и выше равны нулю.

Разность между наименьшим из чисел m и n (матрица А имеет размерность mxn) и рангом матрицы r называется дефектом матрицы.

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

Правило нахождения ранга матрицы:

1. Начиная с миноров первого порядка (элементов матрицы), переходить к минорам больших порядков.
2. Пусть найден минор D r-го порядка, отличный от нуля, тогда нужно вычислить лишь миноры (r+1)-го порядка, окаймляющие минор D. Если все эти миноры равны нулю, то ранг матрицы равен r. Если же хотя бы один отличен от нуля, то эту операцию нужно применять к нему, увеличить ранг матрицы А на 1.

Пример:

Найти ранг матрицы А (4х5)

В матрице содержатся миноры второго порядка, отличные от нуля, например:

Окаймляющий его минор третьего порядка:

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

Таким образом, r=3, дефект равен 1: m-r=1.

3. Клеточные матрицы

Разобьем исходную матрицу на блоки или клетки, или подматрицы

 Клетки:

Тогда

Теорема

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

Процесс нахождения корней

Определяем знаки функции f(x) в ряде точек из области определения функции х₁,х₂,х₃,…, выбор которых учитывается особенностью функции f(x). если окажется, что , то на отрезке [x_k,x_k+1], то имеется по крайней мере один корень уравнения f(x)=0. Необходимо каким-либо способом проверить, является ли этот корень единственным.

Пример:

       Определить действительные корни уравнения:

На отрезке [2,3] имеется корень уравнения, так как  при всех х, то этот корень единственный.

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

Метод хорд

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

За приближенное значение корня принимаем точку пересечения с осью ОХ хорды, проходящей через точки A₀[a₀, f(a₀) ], B₀[b₀, f(b₀) ]

Уравнение хорды:

                           (1)

Точка пересечения a₁ с осью ОХ находится из (1) при у=0 (при этом х=а₁):

                           (2)

Принимая а₁ за конец первого отрезка , можно снова провести хорду и получится приближенное значение а₂

                         (3)

И так далее

                         (4)

Можно показать, что процесс сходится и в пределе .

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

Пусть ξ – корень уравнения f(x)=0 определен на отрезке  причем  и  непрерывны и сохраняют знаки при a<x<b. Найдя какое-нибудь n-ое приближенное значение корня x_n= ξ (a≤x_n≤b), мы можем уточнить его по методу Ньютона.

Положим

                                                                  (1)

Где h_n-малая величина.

По формуле Тейлора, беря только линейные члены находим:

                                  (2)

Так как  - «корень», то

Из (2) следует:

Подставляя h_n в (1), получаем новое приближение корня:

                                           (3)

Так как уравнение касательной в точке B_n[b_n, f(b_n) ]:

Полагая у=0 (корень!); x_n=x_n+1 получим

Поэтому метод Ньютона называют еще методом касательных.

Если в качестве начального приближения выбрать точку а, то получили бы новое приближение, выходящее за интервал . Следовательно «хорошим» начальным приближением x₀ является то, для которого выполнено неравенство:

                                            (4)

Для оценки точности (погрешности) n-го приближения x_n можно воспользоваться следующим соотношением:

,

То есть «установившееся» начальные десятичные знаки приближения x_n и x_n+1,являются верными (следует взять более двух последующих приближений!)

Пример:

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

с пятью верными знаками.

Решение:

Полагая х=0,-10,-100,…, получим f(0)=-10000, f(-10)=-1050, f(-100)≈10⁸

Искомый корень находится в интервале [-100,-10]. Сузим интервал, рассматривая точку х=-11 f (-11)=3453.

Таким образом -11<ξ<-10

На этом интервале и . Так как , то есть , за начальное приближение выбираем х₀=-11.

Результаты вычислений сводим в таблицу:

n	xn	f(xn)
0	-11	3453	-5183	0.7
1	-10.3	134.3	-4234	0.03
2	-10.27	37.8	-4196	0.009
3	-10.261	0.2	-	-

Останавливаемся на n=3. проверяем точность решения, давая приращение . (два знака до запятой, три знака – после)

-5 значащих цифр.

-10261<ξ<-10260

Любое из этих чисел дает искомое приближение. (А хорошо бы еще 1-2 итерации выполнить)

ЛЕКЦИЯ 7

Приближенное решение алгебраических и трансцендентных уравнений (продолжение)

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

(метод последовательных приближений)

Пусть дано уравнение:

f(x)=0                                                        (1)

где f(x) – непрерывная функция. требуется вычислить действительный корень уравнения (1) находящийся на отрезке .

Заменим уравнение (1) на равносильным ему уравнением

                                                              (2)

где  - непрерывна на  функция.

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

Аналогично получаем

Рассмотрим последовательность x₀,x₁,x₂,…,x_n,…

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

Так как уравнения (1) и (2) равносильны, то c-корень и уравнения (1), то есть исходного уравнения.

Выясним при каких значениях процесс сходится.

Теорема

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

 при                   (3)

Тогда итерационный процесс сходится и дает в пределе единственный корень уравнения

Доказательство:

Уравнение  имеет на отрезке  действительный корень. Обозначим его ξ

Выбираем произвольные и строим итерационную последовательность ; ;…; .

Рассмотрим уравнение

.                                                                                                                 (*)

Т.к. ( - корень уравнения , т.е. , а ).

Применяем теорему Лагранжа к уравнению (*).

,

где  лежит между  и , т.е. .

Согласно неравенству (3), имеем

, т.к. .

Аналогично находим

Используя следующее неравенство, получаем

Повторяя процесс, получаем                             

12345678910Следующая ⇒

Поделиться:

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры