Вычислительная математика: Методические указания к проведению практических занятий

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ ÃÎÑÓÄÀÐÑÒÂÅÍÍÎÅ ÎÁÐÀÇÎÂÀÒÅËÜÍÎÅ Ó×ÐÅÆÄÅÍÈÅ ÂÛÑØÅÃÎ ÏÐÎÔÅÑÑÈÎÍÀËÜÍÎÃÎ ÎÁÐÀÇÎÂÀÍÈß

"Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ"

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА Методические указания к проведению практических занятий

Ñàíêò-Ïåòåðáóðã 2003

Составители: Л. А. Решетов, Е. А. Всемирнова, Г. Н. Дьякова, Е. Р. Даниловцева Рецензент канд. физ.-мат. наук, доц. Ю. А. Гусман (кафедра высшей математики Санкт-Петербургского государственного университета аэрокосмического приборостроения)

Методические указания содержат материал к практическим занятиям по дисциплине «Вычислительная математика» и предназначены для использования студентами всех специальностей. Подготовлены кафедрой прикладной математики и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского государственного университета аэрокосмического приборостроения.

© СПбГУАП, 2003

Подписано к печати 17.10.03. Формат 60×84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л.1,62. Уч. -изд. л. 1,46. Тираж 300 экз. Заказ № Редакционно-издательский отдел Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии СПбГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67

2

1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ “РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ” Для успешного выполнения контрольной работы студенты должны владеть элементами линейной алгебры и основами численных методов. Необходимо уметь выполнять действия над векторами и матрицами, находить числовые характеристики векторов и матриц, а также знать основные методы точного и приближенного (итеративного) решения систем линейных алгебраических уравнений. 1.1. Основные теоретические сведения Векторы и матрицы Вектор х задается столбцом n – чисел (компонент). Транспонированный вектор хт задается строкой тех же компонент  x1   .  x =  .  , хТ = ( х1,..., хn ).    .  x   n

(1.1)

Квадратную матрицу А задают в виде таблицы n х n чисел  a11 a12 a a22 A =  21 . .  a a  n1 n 2

. . . .

. . . .

. a1n  . a2 n  . . .   . ann 

(1.2)

Сложение и вычитание векторов и матриц производится поэлементно. При умножении векторов и матриц на число нужно умножать на это число все элементы. Норму вектора в n-мерном векторном пространстве вводят одним из двух способов [1] x 1 = max xi ,

(1.3)

1≤i ≤n

1/ 2

x

2

 n  =  ∑ xi2  i =1   

.

(1.4) 1

Нормы матриц, соответствующие введенным векторным нормам, определяются выражениями Ax , A = Sup x ≠0 x

при этом A 1 = max

n

∑ aij ,

1≤i ≤n j = 1

(1.5)

1/ 2

 n n  A 2 =  ∑ ∑ aij2  . i =1 j =1    Скалярным произведением двух векторов является число

〈 x, y 〉 =

(1.6)

n

∑ xi yi = x ⋅ y cos ϕ,

i =1

(1.7)

где х=
х
2 длина вектора х; y=
y
2 – длина вектора y; ϕ ∈ [0, π] – угол между векторами х и y. При умножении матрицы на вектор получаем вектор, а при умножении двух матриц – матрицу: Ах = у, АВ = С, где yi =

n

∑ aik xk ; cij =

k =1

(1.8)

n

∑ aik bkj .

k =1

Матрица Е называется единичной, если на диагонали у нее – единицы, а остальные элементы нули. Матрица А–1, обратная к матрице А, определяется из соотношения А–1 А = А А–1 = Е.

(1.9)

Эти соотношения являются проверкой для обратной матрицы. Элементы обратной матрицы (А–1)ij находятся по формулам

( ) A −1

2

ij

=

( −1)i + j M det A

ji ,

1 ≤ i, j ≤ n,

(1.10)

где Мji – минор, получаемый вычеркиванием j-й строки и i-го столбца у матрицы А, а определитель матрицы А a11 a det A = 21 . an1 =

n

i +k

∑ aik (−1)

k =1

Mik =

n

a12 a22 . an 2 i +k

∑ aki (−1)

k =1

. . . .

. . . .

M ki =

. . . .

a1n a2 n = . ann n

∑ aki ( −1)k +i Mki .

(1.11)

k =1

Величина ν =
А
·
А–1


(1.12)

называется числом обусловленности матрицы А. Если ν велико, то матрица А называется плохо обусловленной, а если невелико – хорошо обусловленной. Отметим, что ν ≥ 1. Методы решения систем линейных алгебраических уравнений Алгоритмы решения систем линейных алгебраических уравнений можно разделить на две группы: прямые и итерационные. Прямые алгоритмы основываются на точных методах, позволяющих получить решение за конечное число шагов (без учета ошибок округления). Итерационные методы дают точное решение лишь при бесконечном числе шагов, поэтому при их использовании нужно учитывать, что при конечном числе арифметических операций решение всегда получают с некоторой ошибкой, даже если пренебречь ошибками округления при вычислении. Прямые методы решения систем. Метод Гаусса Наиболее распространенным из прямых методов решения является метод Гаусса, который основывается на последовательном исключении неизвестных (число необходимых арифметических операций пропорционально n3). Запишем систему n линейных алгебраических уравнений Ax = b

(1.13)

в виде 3

(0) (0) a11 x1 + a12 x2  (0) (0) a21 x1 + a22 x2  . .  . a (0) x + a (0) x n2 2  n1 1

+ . . . + a1(0) n xn

= b1(0) ,

+ . . . + a2(0) n xn . . . . . .

= b2(0) , . .

(0) + . . . + ann xn

= bn(0) .

(1.14)

Первый этап метода Гаусса (прямой ход) заключается в преобразовании системы (1.14) к “верхнетреугольному” виду. Предположим, что коэффициент неизвестной х1 в первом уравне(0) нии системы (1.14) a11 ≠ 0. Тогда можно исключить переменную х1 из (n–1) уравнений, начиная со второго. Для этого достаточно вычесть из каждого уравнения первое уравнение, умноженное на а(0)21/ а(0)11, а(0)31/ а(0)11, …, а(0)n1/ а(0)11 соответственно, (0) (0) a11 x1 + a12 x2

+ . . . + a1(0) n xn

= b1(0) ,

(1) a22 x2 .

+ . . . + . . . . .

a2(1)n xn .

= b2(1) , . .

an(1)2 x2

+ . . . +

(1) ann xn

=

bn(1) .

(1.15)

(1) Далее, полагая, что коэффициент a22 ≠ 0, выполним аналогичную процедуру исключения переменной х2 в системе уравнений (1) a22 x2 .

+ . . . + a2(1)n xn . . . . . .

= b2(1) , . .

an(1)2 x2

(1) + . . . + ann xn

= bn(1) .

(1.16)

После (n–1)-го шага исключения неизвестных система (1.14) приводится к следующему виду: (0) a (0) 11 x1 + a12 x2 (1) a22 x2 .

+ + .

. . .

. . .

. . .

+ + .

a1(0) n xn (1) a 2 n xn . ( n −1) ann xn

= b1(0) , = b2(1) , . . ( n −1) = bn .

(1.17)

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

( n −1) xn = bn( n −1) / ann ,

 xi =  bi(i −1 −  

n



j =i +1



∑ aij(i−1) x j  / aii(i=1) ,

i = n − 1, n − 2, ..., 1.

(1.18)

Рассмотренный простейший вариант метода Гаусса имеет ряд недостатков [2]. Во-первых, предположения о том, что коэффициенты (0) (1) , … (ведущие элементы) не равны нулю, может оказаться неa11 , a22 выполненным, даже если матрица А является невырожденной (det A ≠ 0), и система должна иметь единственное решение. Тогда приведенный метод решения формально непригоден. Кроме того, ведущие элементы могут оказаться достаточно малыми и после деления на них точность решения системы резко снижается из-за ошибок округления. Для того чтобы избавиться от указанных недостатков, применяют метод исключения Гаусса с выбором ведущего элемента. Этот метод всегда дает единственное решение, если определитель системы отличен от нуля. Кроме того, он менее чувствителен к ошибкам округления. Уменьшение вычислительной погрешности в методе Гаусса с выбором ведущего элемента производится путем перестановки строк и столбцов матрицы А так, чтобы ведущий элемент на k-м шаге исключения был наибольшим по модулю из коэффициентов, участвующих в дальнейшем исключении: ( k −1) akk = max aij( k −1) , 1 ≤ k ≤ n, k ≤i , j ≤ n

(1.19)

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

( k −1) = max aik( k −1) . akk k ≤i ≤ n

(1.20)

Например, для системы уравнений  4 x1 + 5 x2   x1 − 3x2 10 x1 + x2

+ 12 x3 + x3 − x3

= 1, = 2, = 3

5

перед первым шагом исключения требуется, согласно алгоритму с полным упорядочением, поменять первый и третий столбцы системы уравнений: 12 x3 + 4 x1 + 5x2 = 1,   x3 + x1 − 3x2 = 2,  − x3 + 10 x1 + x2 = 3. Согласно алгоритму с частичным упорядочением, необходимо поменять первую и третью строки системы уравнений: 10 x1 + x2 − x3 = 3,   x1 − 3x2 + x3 = 2,  4 x1 + 5 x2 + 12 x3 = 1. Затем выполняется 1-й шаг исключения.

Итерационные методы решения систем линейных алгебраических уравнений Первым шагом в итерационном методе является преобразование исходной системы Ах = b к виду [2–3] Сх = Вх +d,

(1.21)

где матрицы С, В и вектор d определяется по матрице А и вектору b. Причем системы (1.13) и (1.21) являются эквивалентными, т. е. их решения совпадают. Вторым шагом является расстановка индексов в (1.21) и задание нулевого приближения, т. е. Сх(k+1) = Вх(k) + d, k = 0, 1, 2, …,

(1.22)

(0)

где х – заданный вектор. Оценка погрешности k-го приближения определяется соотношением x ( k ) − х∗ ≤ ε,

(1.23)

где х* = А–1b – точное решение системы (1.13). Оценка (1.23) при заданном e > 0 позволяет осуществлять остановку итерационного процесса. Различные итерационные методы отличаются выбором матриц С, В и вектора d. Если С = Е, то метод построения последовательных приближений (1.22) принято называть методом простых итераций. Известен следую6

щий результат о сходимости метода простых итераций [2]: если норма матрицы
В
меньше единицы, то последовательные приближения x(k+1) = Bx(k) + d

(1.24)

сходятся к единственному решению х* системы (1.13) со скоростью геометрической прогрессии при произвольном векторе нулевого приближения х(0). Таким образом, процесс сходится, если выполняется одно из следующих условий [4]:
В
1< 1 или
В
2<1.

(1.25)

Если
В
1< 1, то можно дать оценку погрешности метода простой итерации [5]: k

x ( k ) − x* ≤

B d. 1− B

(1.26)

Оценка (1.26) называется априорной оценкой погрешности итерационного процесса. 1.2. Варианты заданий для выполнения контрольной работы Для выполнения контрольной работы необходимо: а) найти угол между а и b и их нормы; б) найти угол между Аа и Аb и их нормы; в) найти det А, А–1, число обусловленности матрицы А. Вариант I: 1  3 0 3 4 2 2  3  0 −1 −2 0  a =  , b =  , A =  . −1 0 3 1 1 0       1 0 1  0 3 2

Вариант II:  −1   3  2  3  −1  −1  a =  , b =  , A =  1 2 3  −1   4  0      

1 2 1 3

0 3 0 1 . 1 −2   0 0 

7

Вариант III:  −1   −2   −1  0  1  0 a =  , b =  , A =  0 3 3  2   2   0     

3 0 2 1 −2 0  . 1 2 −1   4 0 0

Вариант IV:  −2   0  −1 2 0 0   −1   3  1 −3 1 −1  a =  , b =  , A =  . −2 0 2 −1 0 2         1  0  2 −1 0 0 

Вариант V:  0  2  0  −1   −1   −1 a =  , b =  , A =  −1 2 0  3   −2   0     

0 3 0 2 1 2 . 2 −1 −1   4 1 1 

Вариант VI:  −2   −2   3  1  −2   2 a =  , b =  , A =  −2 3 −1       0  3  0

3 −1 0  0 3 1 . 0 2 −1   2 0 3

Вариант VII:  1  −2   3  0  −2   2 a =  , b =  , A =  −1 0 3      3 3 −      0

3 −1 0  0 3 1 . 0 2 −1   2 0 3

Вариант VIII: 1 0 1  1  −1  2 2  0  1 3 −1 0  a =  , b =  , A =  . 1 2 0 −1 3 −1   0   1   0 1 2 1       

8

Вариант IX: 1  3  2  3 2  1  −1   1 5 2 a =  , b =  , A =  −1 2 0 −1 5  1   0   −1 0 −1     

1 2 . 0   2

Вариант Х:  0  2  3  1  −2   −1 a =  , b =  , A =  −1 −1 2      − 2 1      0

1 −1 4 1 1 6 0 1

0 1 . 1  2

Решить систему линейных уравнений: – методом Гаусса с частичным упорядочением по строкам; – методом итераций с погрешностью, не превышающей ε = 0,01. Одновременно необходимо привести априорную оценку погрешности метода итераций. Вариант I:  x1 =  x2 = x =  3  x4 =

0,23x1 0,42 x1 0,26 x1 0,05x1

− − + −

0,03x2 0,23x2 0,32 x2 0,26 x2

+ + − +

0,21x3 0,06 x3 0,11x3 0,31x3

− − + −

0,17 x4 0,88, 0,62, 0,12 x4

+ 1,14, − 1,17.

+ − + −

0,11x2 0,08 x2 0,17 x2 0,23x2

− + − −

0,34 x3 0,17 x3 0,02 x3 0,07 x3

− − − +

0,16 x4 0,18 x4 0,21x4 0,25 x4

− + + +

0,63, 1,42, 2,23, 0,83,

− + + +

0,15 x2 0,12 x2 0,27 x2 0,18 x2

+ − − −

0,02 x3 0,14 x3 0,02 x3 0,08 x3

+ + − +

0,19 x4 0,25 x4 0,24 x4 0,22 x4

+ − + −

1,83, 0,63, 2,12, 1,13.

Вариант II:  x1 =  x2 = x =  3  x4 =

0,22 x1 0,31x1 0,37 x1 0,12 x1

Вариант III:  x1 =  x2 = x =  3  x4 =

0,32 x1 0,16 x1 0,37 x1 0,12 x1

9

Вариант IV:  x1 =  x2 = x =  3  x4 =

0,41x1 0,11x1 0,12 x1 0,15 x1

− − + −

0,22 x2 0,25 x2 0,08 x2 0,32 x2

+ − − −

0,03x3 0,32 x3 1,14 x3 0,18 x3

+ + − −

0,44, 1,42, 0,24 x4 1,3.

− + − +

0,34 x2 0,23x2 0,12 x2 0,08 x2

− − + +

0,11x3 0,15 x3 0,14 x3 0,05 x3

+ + − +

0,14 x4 0,31x4 0,16 x4 0,57.

− 1,32, + 0,84, − 1,12,

+ − + −

0,22 x2 0,31x2 0,15 x2 0,08 x2

− + − −

0,44 x3 0,15 x3 0,22 x3 0,03x3

− − + +

0,05 x4 0,17, 1,42, 2,35.

+ 2,11,

+ + − +

0,32 x2 0,32 x2 0,17 x2 0,27 x2

− − + −

0,18 x3 0,2 x4 0,05 x3 0,14 x3

+ + − +

0,22 x4 0,62, 0,18 x4 0,95.

− 1,72,

+ − + −

0,27 x2 0,45x3 0,07 x2 0,05 x2

− + + +

0,22 x3 0,18 x4 0,29 x3 0,06 x3

− − + −

0,18 x4 0,33, 0,12 x4 0,28 x4

− 0,48, − 0,17.

− + − −

0,07 x2 0,03x2 0,07 x2 0,41x2

+ + + −

0,38 x3 0,11x3 0,09 x3 1,21.

− 0,21x4 − 0,32 x4 − 0,11x4

− 0,81, − 0,64, + 1,72,

− 0,81,

Вариант V:  x1 =  x2 = x =  3  x4 =

0,18 x1 0,12 x1 0,05 x1 0,12 x1

Вариант VI:  x1 =  x2 = x =  3  x4 =

0,13x1 0,23x1 0,06 x1 0,72 x1

Вариант VII:  x1 =  x2 = x =  3  x4 =

0,17 x1 −0,19 x1 0,32 x1 0,12 x1

+ 0,89,

Вариант VIII:  x1 =  x2 = x =  3  x4 =

0,13x1 −0,21x1 0,12 x1 0,33x1

+ 1,21,

Вариант IX:  x1 =  x2 = x =  3  x4 =

10

0,19 x1 −0,23x1 0,51x1 0,33x1

Вариант X:  x1 =  x2 = x =  3  x4 =

− − + −

0,22 x1 0,38 x1 0,11x1 0,17 x1

0,12 x3 0,05 x3 0,23x2 0,21x2

+ + − +

+ − + −

0,31x4 0,22 x4 0,31x4 0,31x3

2,2, 1,5, 1,2, 0,17.

1.3. Пример выполнения задания Дано: 2 1 2 1 0 1 a =  , b =  , A =  0 2 1      1  3 0

1 1 3 −1 0 4 2 1

0 1  . 0  0

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

{

= 0,72 x1 − 0,1x2 = 0,3x1 + 0,02 x2

x1 x2

+ 1,2, − 0,5.

Найдем угол между a и b и их нормы a 1 = max {2,1,0,1} = 2, b 1 = max {1,0,2,3,} = 3,

2

=

2

=

a

b

n

∑ ai2 =

22 + 12 + 12 = 6,

i =1 n

∑ bi2 =

12 + 22 + 32 = 14.

i =1

Скалярное произведение векторов а и b a, b =

n

∑ aibi = 2 ⋅1 + 1 ⋅ 0 + 0 ⋅ 2 + 1 ⋅ 3 = 5. i =1

Так как a = a

2

= 6 и b = b

2

= 14 , то

11

cos ϕ =

a, b 5 = = 0,545, a⋅b 6 ⋅ 14

ϕ = arccos(0,545) = 57o. Найдем угол между Аа и Аb и их нормы 2 1 Aa =  1  0 

1 1 3 −1 0 4 2 1

0  2   2 ⋅ 2 1  1   1 ⋅ 2 = 0  0   1 ⋅ 2     0   1   0 ⋅ 2

+ + + +

1 ⋅1 3 ⋅1 0 ⋅1 2 ⋅1

+ − + +

1⋅ 0 1⋅ 0 4⋅0 1⋅ 0

+ + + +

0 ⋅1  5  1⋅1   6  = , 0 ⋅1  3     0 ⋅1  2 

2 1 Ab =  1  0 

1 1 3 −1 0 4 2 1

0  1   2 ⋅ 1 1  0   1 ⋅ 1 = 0  2   1 ⋅ 1     0   3   0 ⋅ 1

+ + + +

1⋅ 0 3⋅ 0 0⋅0 2⋅0

+ − + +

1⋅ 2 1⋅ 2 4⋅2 1⋅ 2

+ + + +

0 ⋅ 3  4  1⋅ 3   2  = , 0 ⋅ 3  7     0 ⋅ 3  2 

Aa 1 = max {5,6,3,2} = 6,

Ab 1 = max {4,2,7,2} = 7, Aa

Ab

2

2

= 52 + 62 + 32 + 22 = 74 = 8,6,

= 42 + 22 + 72 + 22 = 73 = 8,54, ,

Aa, Ab = 5 ⋅ 4 + 6 ⋅ 2 + 3 ⋅ 7 + 2 ⋅ 2 = 57, , cos ϕ =

Aa, Ab 57 = = 0,775, . Aa ⋅ Ab 74 ⋅ 73

ϕ = arccos 0,775 = 39o.. Найдем det A,A–1, число обусловленности ν. Определитель матрицы det А разложим по элементам четвертого столбца 2+ 4

det A = ( −1)

12

2 1 1 1 0 4 = −15. 0 2 1

Миноры элементов матрицы А 3 −1 1 1 −1 1 1 3 1 M11 = 0 4 0 = −8, M12 = 1 4 0 = 1, M13 = 1 0 0 = 2, 2 1 0 0 1 0 0 2 0 1 3 −1 1 1 0 2 1 0 M14 = 1 0 4 = −13, M 21 = 0 4 0 = 0, M 22 = 1 4 0 = 0, 0 2 1 2 1 0 0 1 0 2 1 0 2 1 1 1 1 0 M 23 = 1 0 0 = 0, M 24 = 1 0 4 = −15, M 31 = 3 1 1 = 1, 2 2 0 0 2 1 2 1 0 2 1 0 2 1 0 2 1 1 M 32 = 1 −1 1 = −2, M 33 = 1 3 1 = 4, M 34 = 1 3 −1 = 11, 0 1 0 0 2 0 0 2 1 1 1 0 2 1 0 2 1 0 M 41 = 3 −1 1 = −4, M 42 = 1 −1 1 = −7, M 43 = 1 3 1 = 1, 0 4 0 1 4 0 1 0 0

M 44

2 1 1 = 1 3 −1 = 16. 1 0 4

Обратная матрица 0 1 4  −8  − −7  1 0 2 1 A −1 = .  2 0 −4 −1  −15    13 −15 −11 16   

Проверка 0 1 4 2  −8 0 2 −7   1 1  −1 ⋅ A A=−  0 −4 −1   1 15  2  13 −15 −11 16   0    −1

1 1 3 −1 0 4 2 1

0 1 1  0 = 0 0   0   0

0 1 0 0

0 0 1 0

0 0 . 0  1 

13

Нормы матриц А и А–1 n

A 1 = max ∑ aij = max {4,6,5,3} = 6, 1≤i ≤n

A

2

j =1

 n  =  ∑ aij2   i, j   

A −1 = max 1

1

2

= 6,32,

{1513 , 1015 , 157 , 1555} = 3,66,

A −1

2

= 2,03.

Число обусловленности ν1 = A 1 ⋅ A −1 = 21,9, 1

ν 2 = A 2 ⋅ A −1

2

= 12,8.

Для решения системы линейных уравнений методом исключения Гаусса приведем ее к стандартному виду Ах = b. С этой целью перенесем неизвестные из правой части уравнения в левую 0,28 x1 + 0,1x2 = 1,2,  0,3x1 − 0,98 x2 = 0,5. Так как коэффициент при неизвестной х1 во втором уравнении больше чем в первом, произведем перестановку строк 0,3 x1 − 0,98 x2 = 0,5,  0, 28 x1 + 0,1x2 = 1, 2. Решением системы уравнений являются следующие значения неизвестных х*=(4,027; 0,723)Т. Для исходной системы уравнений 0,72 −0,1   1,2  B =   , d =  −0,5  . 0,3 0,02    

14

Нормы матрицы
В
1 = 0,82 и
В
2 = 0,79. Следовательно, выполнены условия сходимости алгоритма простой итерации (1.25). В дальнейшем, для определенности, будем использовать норму
В
1. Полагая в качестве нулевого приближения вектор х(0) = (0,0)Т, выполним несколько последовательных шагов итерационного процесса в соответствии с выражением (1.24). Результаты расчетов приведены в таблице. k

2

4

6

8

10

14

18

x1( k )

2,114

3,157

3,632

3,848

3,946

4,011

4,024

x2( k )

-0,15

0,324

0,541

0,64

0,685

0,715

0,721

x ( x ) − x∗

1,913

0,87

0,395

0,179

0,081

0,016

0,003

4,483

3,014

2,027

1,363

0,916

0,414

0,187

∆(k)

Кроме того, построим зависимости нормы вектора х(k) – х* и оценки k

погрешности метода простой итерации

∆

(k )

=

B d от номера 1− B

итерации k. Данные таблицы показывают, что требуемая точность вычислений ε = 0,01 достигается при k = 16.

15

2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ “ПРИБЛИЖЕНИЕ ФУНКЦИЙ” При изучении зависимостей между величинами важной задачей является приближенное представление (аппроксимация) этих зависимостей с помощью известных функций или их комбинаций, подобранных надлежащим образом. В данной контрольной работе необходимо построить функцию, которая была бы “достаточно близка” к приближаемой функции в среднеквадратическом. Для выполнения контрольной работы студенты должны изучить теорию приближения функций, знать общие правила интегрирования и уметь решать системы линейных уравнений. 2.1. Основные теоретические сведения Пусть имеется система линейно-независимых функций ϕ1 , ϕ2 , ..., ϕm . Напомним, что система функций является линейно-независимой, если из равенства α1ϕ1 + α2ϕ2 + ... + αm ϕm = 0

следует, что все коэффициенты α1 , α2 , ..., αm равны нулю. Для приближаемой функции f(x) многочлен Φm ( x) =

m

∑ ck ϕk ( x )

k =1

(2.1)

называется многочленом наилучшего среднеквадратичного приближения, если квадрат расстояния от него до функции f(x) является наименьшим среди многочленов вида (2.1)

(

)

ρ2 f , Φ*m ( x ) =

Здесь ρ2 ( f , Φ ) =

min ρ2 ( f , Φ m ( x ) ) . 

c1 ,c2 , ...,cm 

b

∫ ( f ( x) − Φ( x) ) dx. 2

a

Можно показать [6], что коэффициенты с1, с2, …, сm, минимизирующие квадрат расстояния ρ2 ( f , Φ ) , должны удовлетворять системе линейных уравнений 16

 a11c1 + a12 c2  a21c1 + a22 c2  . . .  a c + a m 2 c2  m1 1

+... + a1m cm +... + a2m cm . . +... + amm cm

b

b

a

a

= b1, = b2 , . . = bm .

(2.2)

aij = ϕi ( x )ϕ j ( x )dx, bi = ∫ ϕi ( x ) f ( x )dx, 1 ≤ i, j ≤ m.

∫

Систему уравнений (2.2) называют нормальной системой. Благодаря предположению о линейной независимости функций ϕ1, ϕ2 ,..., ϕm решение системы (2.2) всегда существует и единственно. Заметим, что степенные функции 1, х, …, хm–1 линейно-независимы при любом m на любом конечном отрезке [a, b]. 2.2. Варианты заданий для выполнения контрольной работы Приближаемая функция f(x) задается в виде F(x) = 0,1β + 0,3βx + sin x.

(2.3)

Для х ∈ [0, π/2]. Величина в совпадает с номером варианта задания. При выполнении контрольной работы № 2 необходимо: а) найти элементы вектора с = (с1, с2, …, сm)T наилучшего среднеквадратического приближения Φm ( x) =

m

∑ ck ϕk ( x )

k =1

m −1 по системе степенных функций ϕ1 ( x ) = 1, ϕ2 ( x ) = x, ..., ϕm ( x ) = x для двух значений m, равных 2 и 3; б) вычислить значение квадрата расстояния от Фm(х) до приближаемой функции f(x), т. е. ρ22 при m = 2 и ρ32 при m = 3; в) определить величину относительного уменьшения ошибки аппроксимации δ = ρ3 / ρ2 .

2.3. Пример выполнения задания Найдем многочлен наилучшего среднеквадратичного приближения для функции f(x) = sinx. Для расчета коэффициента нормальной системы уравнений необходимо воспользоваться справочниками, содержа17

щими таблицы интегралов от степенных и тригонометрических функций [7]. Напомним, что π

2

∫ 0

π

sin xdx = 1,

2

∫

π

x sin xdx = 1,

0

2

∫

π

x sin xdx = π − 2, 2

0

2

∫ sin 0

2

x dx =

π . 4

1) m = 2. В наших обозначениях ϕ1 = 1, ϕ2 = x. Коэффициенты нормальной системы уравнений 2 3 π , a12 = a21 = π , a22 = π . 2 8 24 Получаем систему уравнений относительно неизвестных с1 и с2:

a11 =

π  2 c1 +  2  π c1 +  8

π2 c2 8 π3 c2 24

= 1, = 1.

Решая систему, получим 8π − 24 96 − 24π ≈ 0,11, c2 = ≈ 0,66. 2 π π3 Многочлен наилучшего приближения c1 =

Ф2(х) = 0,11 + 0,66х. 2) m = 3. Нормальная система уравнений π  2 c1 +  2 π  c1 +  83 π c +  24 1

π2 c2 8 π3 c2 24 π4 c2 64

π3 c3 24 π4 + c3 64 π6 c3 + 160 +

=

1,

=

1,

= π − 2.

Решение системы с1 = 0, с2 = 1,1, с3 = –0,277. 18

Многочлен наилучшего приближения Ф3 (х) = 1,1х – 0,277х2. Следует заметить, что вычисления коэффициентов многочлена необходимо проводить с точностью до третьего знака после запятой. Вычислим квадрат расстояния от приближаемой функции f(x) = sinx до многочлена наилучшего приближения π

ρ22

=

2

∫ (sin x − 0,11 − 0,66 x )

2

dx ≈ 0,108,

0

π

ρ32

=

2 ∫ (sin x − 1,1x + 0,277 x ) 2

2

dx ≈ 0,01.

0

Относительное уменьшение ошибки аппроксимации δ = ρ3 / ρ2 = 0,307.

Видно, что ошибка аппроксимации функции sinx многочленом Ф3(х) почти в три раза меньше, чем при аппроксимации многочленом Ф2(х).

19

3. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ “РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ” Пусть некоторая функция y = f(x) при a ≤ x ≤ b определена и непрерывна. Предположим, что имеются два числа x 1 и x 2 такие, что

a ≤ x1 < x2 ≤ b . Если f(x1) и f(x2) имеют противоположные знаки, то между x1 и x2 существует хотя бы один корень функции f(x). 3.1. Основные теоретические сведения Нелинейное уравнение f(x) = 0 можно эквивалентным преобразованием многими способами привести к виду g(x) = h(x). Построение сходящейся числовой последовательности

(

) (

)

{x( )} m

∞

m=0

по правилу

g x ( m +1) = h x ( m ) при заданном xi( ) называется итерационным методом вычисления корня xN. Вследствие предполагаемой непрерывности предельное значение такой последовательности является корнем, потому что из основных 0

m m +1 соотношений lim x ( ) = a и lim x ( ) = a в силу непрерывности g и m→∞

m→∞

h имеем g(a) = h(a), т. е. a = xN. Достаточные условия сходимости: g’(x) и h’(x) непрерывны в некоторой окрестности xN, x(0) лежит в этой окрестности, и в этой окрестности g ′ ( x ) > h′ ( x ) . Выбором функций g(x) и h(x) можно получить ряд хорошо сходящихся методов. Метод Ньютона

g ( x ) = x, h ( x ) = x −

f (x) . f ′( x )

(3.1)

f ′′ f < 1 в окрестносf ′2 ти xN. Если xN является простым корнем, то выполняются соотношения 20

Сходимость имеет место тогда, когда h′ ( x ) =

f ′ ( x N ) ≠ 0 и h′ ( x N ) ≠ 0 . Следовательно, для начального значения x(0)

должно выполняться неравенство

( ) ( )

( )

0 0 0 f ′′ x ( ) f x ( ) < f ′ x ( )

2

.

(3.2)

Итерационная формула имеет вид x

(m +1)

=x

(m )

( ), f ′(x( ) ) m f x( )

−

m

( )

m f ′ x ( ) ≠ 0.

(3.3)

Метод секущих (правило ложного положения, метод хорд)

x

(m +1)

=x

(m )

sm =

−

( )

m f x( )

(m = 1,

sm

( ) (

m m −1 f x( ) − f x( ) m m −1 x( ) − x( )

2, ... ) ,

(3.4)

). ( ) ( )

Здесь x(0) и x(1) – два заданных числа таких, что f x (0) f x (1) < 0 . Простая итерация

(

)

Если g(x) = x, то x (m +1) = h x ( m ) ; условие сходимости h ′ ( x ) < 1 . Если x(m) достаточно близко к xN, то для погрешности r (m ) = x N − x (m ) справедливо следующее соотношение:

(

)

m m m −1 0 r ( ) ≈ h ′ ( x N ) r ( ) ≈ ( h ′ ( x N )) x N − x ( ) .

(3.5)

3.2. Варианты заданий для контрольной работы Задание 1 Отделить корни уравнения f(x) = 0 графически и уточнить один из них методом итераций [7] с точностью не хуже ε = 10−4 Предваритель21

но определить минимально необходимое для этого количество итераций. Оценить фактическую точность полученного решения. 16. x = (x+1)3. 1. ln(x)+(x+1)3=0. x 17. x2 = sin(x). 2. x2 =1. 3.

1 x +1 = . x

4.

x – cos(x) = 0

18. x3 = sin(x). 19. x = log ( x + 2 ).

5. 3x + cos(x)+1 = 0 20. x2 = ln(x+1). 6. x+ln(x)=0,5. 21. 2x+log(x) = –0,5. 7. 2 – x = ln(x). 22. 2x + cos(x) = 0,5. 23. sin(0,5x) + 1 = x2. 8. (x – 1)2 = 0,5 ex. x 24. 0,5x + log(x – 1)0,5. 9. (2 – x)e = 1. x 25. sin(0,5 + x) = 2x – 0,5. 10. 2,2x – 2 = 0. 11. 2x – ln(x) = 7. 26. log(2+x)+2x = 3. 27. log(1+2x) = 2 – x. 12. x2+4sin(x) = 0. 13. 5x – 8 ln(x) = 8. 28. 2sin(x – 0,6) = 1,5 – x. 29. x + log(1 + x) = 1,5. 14. 3x – ex =0. 30. x + cos(x) = 1. 15. x(x+1)2 = 1. Задание 2 Отделить корни уравнения графически и уточнить один из них методом Ньютона [7]. Вести вычисления с пятью десятичными цифрами. Определить точность полученного решения. 1. x – sin(x) = 0,25. 16. tg(0,3x + 0,4) x2. 17. x2 – 2sin(x) = 0. 2. tg(0,58x + 1) = x2.

4.

tg(0,4x + 0,4) = x2.

1 ctg ( x ) − x = 0. 3 19. tg(0,47x + 0,2) = x2.

5.

log ( x ) −

20. x2 + 4sin(x) = 0.

6.

tg(0,5x + 0,2) = x2.

7. 8. 9.

3x – cos(x) – 1 = 0. x + log(x) = 0,5. tg(0,5x + 0,1) = x2.

3.

22

x − cos (0,387 x ) = 0. 7 = 0. 2x + 6

18.

ctg ( x ) −

x = 0. 2 22. 2x – log(x) – 7 = 0. 23. tg(0,44x + 0,3) = x2. 24. 3x – cos(x) – 1 = 0.

21.

25.

ctg ( x ) −

11. ctg(1,05x) – x2 = 0. 12. tg(0,4x + 0,3) = x2. 13. xlog(x) – 1,2 = 0.

x = 0. 10 26. x2 +4cos(x) = 0. 27. tg(0,36x + 0,4) = x2. 28. x + log(x) = 0,5.

14. 1,8 x2 – sin(10x) = 0.

29.

ctg ( x ) −

15. ctg ( x ) −

30.

 2log ( x ) − x  + 1 = 0.   2 

10. x2 + 4sin(x) = 0.

x = 0. 4

x = 0. 5

3.3. Пример выполнения задания Задание 1 2x + log(2x + 3) = 1.

4

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

2

log(2x + 3) = 1 – 2x

y = log2x+3 –1

(см. рис.1). Из графика видно, что уравнение имеет один корень, лежащий в промежутке [0; 0,5]. Для уточнения его методом итераций приведем уравнение к виду x = ϕ(x). Функцию ϕ(x) будем искать из соотношения

1

2 y =1 – 2 · x

–2

–4

ϕ ( x ) = x − f ( x ) k , где k ≥ M 2 и

Рис.1

принято обозначение M = max

x∈[0; 0,5]

f ′( x ) ;

число k имеет тот же знак, что и f '(x) в промежутке [0; 0,5]. (Итерационный метод, получаемый при этом, обычно называют методом релаксации). Находим f ( x ) = 2 x + log (2 x + 3) − 1 , f ′ ( x ) = 2 + 2

0,4343 (используя 2x + 3

равенство log a = 0,4343ln a , a > 0). 23

M = max

x∈[0; 0,5]

f ′( x ) = 2 +

0,8686 ≈ 2,2895, 2⋅0 + 3

f '(x) > 0 при x ∈ [0; 0,5] . Примем k = 2, тогда

1 1 1 1 ϕ ( x ) = x − f ( x ) 2 = x − x − log (2 x + 3) + = − log (2 x + 3). . 2 2 2 2 За начальное приближение возьмем x0 = 0 (естественно, начальное приближение выбирается из данного промежутка), все остальные приближения будем определять из равенства xn +1 = ϕ ( xn ) =

1 1 − log (2 x + 3) , n = 0, 1, 2, … . 2 2 Минимальное число итераций nmin, необходимое для получения заданной точности решения ε, определим по формуле  ln ((1 − q ) ε x0 − x1 )  nmin = 1 + , ln q   где [α] – целая часть числа α. Число q удовлетворяет неравенству max ϕ′ ( x ) ≤ q < 1.

1 0,8686 ≈ 0,1448. Находим max ϕ′ ( x ) = max ⋅ 0≤ x ≤0,5 0≤ x ≤0,5 2 2 x + 3

Выберем q = 0,15, тогда x1 = ϕ ( x0 ) =

1 1 − log 3 ≈ 0,26 . 2 2

Для заданного ε = 10–4 получаем nmin

(

 ln (1 − 0,15) ⋅ 10−4 0 − 0,26 = 1 + ln 0,15  

)  = [1 + 4,23] = 5.  

Таким образом, для достижения точности ε = 10–4 необходимо сделать не менее пяти итераций. Проведем все вычисления с пятью десятичными цифрами и определим x∗ ≈ x6 = 0,230410 . Фактическую точность полученного решения можно оценить по формуле 24

x ∗ − xn <

q xn − xn −1 . 1− q

Для n = 6 получаем 0,15 10−5 ≈ 2 ⋅ 10−6. 1 − 0,15 Столь высокая точность результата объясняется малостью числа q = 0,15 по сравнению с единицей. x∗ − x6 <

Ответ: x∗ = 0,230410 ± 0,000002 . Задание 2 tg(0,55x + 0,1) = x2.

1,5 1,25 1 0,75 y = tg 0,55x +0,1 0,5 0,25

y = x2

Отделим корень графически. Построим графики функций y1(x) = tg(0,55x + 0,1), y2(x) = x2 (см. рис. 2). Положительный корень уравнения заключен в промежутке [0,6;0,8]. 0,2 0,4 0,6 0,8 1 1,2 x* Уточним корень методом Ньютона. Перепишем уравнение Рис. 2 в виде f(x) = 0, где f ( x ) = tg(0,55 x + 0,1) − x 2 . Дифференцируя, получаем выражения для производных

f ′( x ) = f ′′ ( x ) = −

0,55 − 2 x, cos (0,55 x + 0,1) 2

0,552 sin(0,55 x + 0,1) − 2. 2cos3 (0,55 x + 0,1)

В методе Ньютона за начальное приближение выбирают такое число из промежутка, для которого верно неравенство f ( x ) f ′′ ( x ) > 0.

25

Так как f (0,6 ) ≈ 0,1 > 0 , f (0,8 ) ≈ −0,04 < 0 и f ′′ ( x ) < 0 при x ∈ [0,6; 0,8] , то за начальное приближение примем x0 = 0,8. Уточнение производим по формуле xn +1 = xn −

f ( xn ) , n = 1, 2, ... . f ′ ( xn )

В результате получаем: x1 = 0,75240, x2 = 0,75019, x3 = 0,75019. Таким образом, x∗ ≈ x2 = 0,75019 . Оценим точность полученного результата, воспользовавшись формулой x ∗ − xn <

M2 ( xn − xn −1 )2 , n = 1, 2, 3, ..., 2m1

где числа m1, M2 удовлетворяют неравенствам

0 < m1 ≤

min

x∈[0,6; 0,8]

f ′( x ) , M 2 ≥

max

x∈[0,6; 0,8]

f ′′ ( x ) .

После вычислений получаем

min

x∈[0,6; 0,8]

f ′ ( x ) ≈ 0,54,

max

x∈[0,6; 0,8]

f ′′ ( x ) ≈ 2,1.

Выберем m1 = 0,5, M2 = 2,2, тогда x ∗ − x2 <

M2 ( x2 − x1 )2 ≈ 1,1 ⋅ 10−5. 2m1

Ответ: x ∗ = 0,75019 ± 0,000011 .

26

Библиографический список 1. Фарафонов В. Г. Вычислительная математика и программирование: Метод указ. по алгоритмизации задач линейной алгебры /ЛИАП. Л., 1984. 36 с. 2. Боглаев Ю. П. Вычислительная математика и программирование. М.: Высш. шк., 1990. 544 с. 3. Турчак Л. И. Основы численных методов. М.: Наука, 1987. 387 с. 4. Алимов А. Л., Понырко С. А., Потоцкий В. К. Вычислительная математика и программирование: Метод указ. к выполнению курсовой работы / ЛИАП. Л., 1982. 53 с. 5. Воробьева Г. Н., Данилова А. Н. Практикум по вычислительной математике. М.: Высш. шк., 1990. 208 с. 6. Стрепетов А. В., Табанов М. Б., Щадилов А. Е. Вычислительная математика. Методы приближения функций: Метод. указ. / ЛИАП. Л., 1989. 33 с. 7. Бронштейн И. Н., Семендяев К. А. Справочник по математике. М.: Изд-во физ.-мат. лит., 1959. 608 с.

27

Оглавление 1. Методические указания к выполнению контрольной работы “Решение систем линейных уравнений” ......................................... 1.1. Основные теоретические сведения .......................................... Векторы и матрицы ................................................................... Методы решения систем линейных алгебраических уравнений .................................................................................... Прямые методы решения систем. Метод Гаусса ..................... Итерационные методы решения систем линейных алгебраических уравнений ........................................................ 1.2. Варианты заданий для выполнения контрольной работы ..... 1.3. Пример выполнения задания ..................................................... 2. Методические указания к выполнению контрольной работы “Приближение функций” .................................................................. 2.1. Основные теоретические сведения .......................................... 2.2. Варианты заданий для выполнения контрольной работы ..... 2.3. Пример выполнения задания ..................................................... 3. Методические указания к выполнению контрольной работы “Решение нелинейных уравнений” .................................................. 3.1. Основные теоретические сведения .......................................... Метод секущих (правило ложного положения, метод хорд) .. Простая итерация ........................................................................ 3.2. Варианты заданий для контрольной работы ........................... 3.3. Пример выполнения задания ..................................................... Библиографический список ...................................................................

28

1 1 1 3 3 6 7 11 16 16 17 17 20 20 21 21 21 23 27