Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
аукциона на право заключить договор купли-продажи объекта движимого имущества - легковой автомобиль ВАЗ- 30, являющегося муниципальной собственностью ...полностью>>
'Конкурс'
Проведение Европейской недели местной демократии с 14.10.2013 г. по 20.10.2013 г. в Валуйском районе было призвано усилить понимание того, что местная...полностью>>
'Документ'
Современный школьник две трети свободного от учебных занятий времени проводит за просмотром телепередач. День и ночь на телевидении бушует многоцветны...полностью>>
'Документ'
Организатором районных соревнований по спортивному туризму среди учащихся является Муниципальное автономное образовательное учреждение детско-юношеска...полностью>>

Главная > Решение

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Практический курс вычислительной алгебры

Загускин В. Л.

2013 г

Предисловие 4

1 Линейная алгебра 5

1.1 Основные понятия и теоремы линейной алгебры 5

1.1.1 Линейное пространство 5

1.1.2 Операции с векторами 5

1.1.3 Линейная зависимость векторов, базис 6

1.1.4 Скалярное произведение векторов 7

1.1.5 Линейная функция и линейный оператор 8

1.1.6 Матрицы 8

1.1.7 Определитель 11

1.1.8 Собственные векторы и собственные числа оператора 12

1.1.9 Система линейных уравнений 14

Решение системы при n = m 14

Решение системы при n < m 15

Решение системы при n > m , принцип наименьших квадратов 15

1.2 Погрешности вычислений 15

1.2.1 Погрешность округления 16

1.2.2 Погрешность начальных данных. Обусловленность 16

1.2.3 Обусловленность матрицы Гильберта 18

1.2.4 Погрешность решения квадратного уравнения 18

1.2.5 Погрешность элементарных операций с векторами 19

1.2.6 Погрешность ортогонализации 19

Ортогонализация Шмидта 19

Неортогональность векторов при ортогонализации Шмидта 20

Двойная ортогонализация 21

1.3 Численные методы в программе LAP 21

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

Метод Гаусса 22

Метод двойной ортогонализации 22

1.3.2 Вычисление определителей 24

1.3.3 Вычисление обратной матрицы 25

1.3.4 Построение характеристического полинома матрицы 26

Метод Крылова 26

Метод интерполяции 30

1.3.5 Определение собственных чисел. Метод Якоби 31

1.3.6 Определение собственного вектора 33

Метод прямых итераций 33

Метод обратных итерации 34

2 Полиномы 35

2.1 Операции с полиномами 36

2.1.1 Сложение и умножение полиномов 36

2.1.2 Деление полиномов. Схема Горнера 36

2.1.3 Вычисление значения полинома в точке 36

2.1.4 Понижение степени полинома. Число корней 37

2.1.5 Замена аргумента полинома 37

2.1.6 Вычисление производной 37

2.1.7 Вычисление значений полинома 37

2.2 Полином в форме Лагранжа 37

2.3 Преобразование форм представления полинома 38

2.4 Корни полинома 41

2.4.1 Погрешность округлений, область неопределенности 41

2.4.2 Определение границ вещественных корней методом Ньютона 42

2.4.3 Определение границ комплексных корней методом аргумента 43

2.4.4 Вычисление вещественных корней методом Рыбакова 43

2.4.5 Вычисление комплексных корней методом минимума на сетке 46

2.4.6 Вычисление комплексных корней методом аргумента 49

2.4.7 Уточнение корней методом Ньютона 51

2.4.8 Исключение корней 53

3 Полиномиальная аппроксимация 54

3.1 Среднеквадратичное приближение 55

3.2 Равномерное приближение 57

3.3 Аппроксимация функций с разрывом производной 59

4 Программа LAP, главная форма, основные понятия 62

4.1 Объекты матриц 62

4.2 Текстовые окна 62

4.3 Настройки для полиномов 63

4.4 Графическое окно 63

4.5 Меню 63

4.6 Работа с мышью 65

Список использованных источников 67

Предисловие

Предлагаемый электронный учебник "Практический курс вычислительной алгебры" состоит из книги LAP-book и прикладной программы LAP. Аббревиатура LAP составлена из первых букв слов Linear, Algebra, Polynomials, которые раскрывают основное содержание учебника.

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

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

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

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

Более полное изложение рассматриваемых в данном курсе методов можно найти в работах автора [], [2], [], [], [] и работе Л. М. Рыбакова []. Обстоятельное изложение вопросов точности методов вычислительной алгебры содержится в книге Дж. Уилкинсона [].

Автор благодарен О. В. Дрыжаковой, которая в процессе редактирования книги внесла ряд ценных изменений. Программа LAP написана автором совместно с Е. В. Гареевой и О. В. Дрыжаковой.

Отзывы и замечания просьба присылать по адресу zaguskin-vladimir@yandex.ru

1Линейная алгебра

1.1 Основные понятия и теоремы линейной алгебры

1.1.1Линейное пространство

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

a = ( a1, a2, …, an)

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

a = ( a0, a1, …, an-1)

Векторы, в отличие от чисел, будем изображать жирным шрифтом. Числа (их называют координатами вектора), как правило, будем считать вещественными, хотя в некоторых приложениях нам понадобятся комплексные координаты. Число координат n у всех векторов одного пространства должно быть одинаковым, оно называется размерностью пространства. В геометрических пространствах n = 1, 2 или 3. В функциональном анализе рассматриваются пространства бесконечной размерности. В алгебре мы будем рассматривать задачи, размерность которых составляет от нескольких единиц до нескольких десятков.

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

1.1.2Операции с векторами

Не уточняя деталей, отметим, что в алгебраическом пространстве операции над векторами сводятся к операциям над их координатами:

k a = (ka1, ka2, …, kan),

a + b = (a1 + b1, a2 + b2, …, an + bn).

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

k ( a1, a2, …, an) = (ka1, ka2, …, kan),

a + b = b + a, (a + b) + c = a + (b + c)

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

1.1.3Линейная зависимость векторов, базис

Понятие линейной зависимости является ключевым в теории линейных пространств. Система векторов a, b, …, c называется линейно зависимой, если хотя бы один из этих векторов можно выразить через остальные, например, a = r b + … + s c . Выражение, стоящее в правой части, называется линейной комбинацией входящих в него векторов.

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

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

Критерий линейной зависимости можно перефразировать следующим образом. Система является линейно зависимой, если существует линейная комбинация, равная нулю и не все коэффициенты этой комбинации равны нулю. Очевидно, те векторы, коэффициенты при которых отличны от нуля, можно выразить через остальные. Эту формулировку удобнее использовать, если не требуется выделять один из векторов.

Система векторов называется базисом, если она линейно независима, но любой вектор пространства может быть выражен через векторы этой системы. Важным примером служит канонический базис e1 = (1, 0, …, 0), e2 = (0, 1, …, 0), …, en = (0, 0, …, 1).

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

a = (a1, a2, …, an) = a1 e1 + a2 e2 + …+ an en

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

Укажем без доказательства, что в n – мерном пространстве существует множество базисов, и все они содержат одинаковое число векторов, равное размерности пространства. Верно и обратное – любая линейно независимая систем из n векторов является базисом. Коэффициенты разложения произвольного вектора по векторам базиса также принято называть координатами вектора в этом базисе. В некоторых приложениях, например, в тензорном исчислении, вопросам преобразования координат при переходе от одного базиса к другому, уделяется много внимания. Мы подробно на этом останавливаться не будем.

1.1.4Скалярное произведение векторов

Скалярное произведение является линейной функцией двух векторных аргументов. Оно часто используется, поэтому для его обозначения принято применять специальный знак - круглые скобки. Определяется оно через координаты векторов: (a, b) = a1 b1 + a2 b2 + … + an bn

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

| a | = √(a,a)

В геометрии скалярное произведение можно трактовать как произведение длин векторов на косинус угла между ними. Этой терминологией можно пользоваться и в многомерном случае. Аналогично мы будем называть проекцией вектора b на направление вектора a вектор

p = (a, b) / (a, a) ∙ a

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

q = b - (a, b) / (a, a) ∙ a

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

1.1.5Линейная функция и линейный оператор

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

f(ka) = k f(a), f(a + b) = f(a) + f(b)

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

A(kx) = k Ax,

A(x + y) = Ax + Ay.

В силу линейности для определения оператора достаточно задать результат его действия на векторы канонического базиса:

a1 = A e1, a2 = A e2, … , an = A en.

Тогда для любого вектора x:

y = Ax = A(x1 e1 + x2 e2 + … + xn en ) = x1 a1 + x2 a2 + … + xn an .

Координаты векторов ak принято записывать в виде таблицы, так называемой, матрицы:

Первый индекс элемента матрицы является номером координаты вектора ak, второй индекс – номером вектора. Таким образом, каждый вектор изображается столбцом матрицы. Строка матрицы содержит координаты с одинаковыми номерами всех векторов. Вычисление координат вектора y можно представить, как последовательное вычисление скалярных произведений строк матрицы A с вектором x:

,

,

…………………………………

.

1.1.6Матрицы

Матрицей называется прямоугольная таблица чисел вида:

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

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

Главная диагональ матрицы

Главной диагональю квадратной матрицы называют совокупность элементов a11 ,a22 ,…, ann.

Симметричные матрицы

Элементы aik и aki называются симметричными. В записи матрицы они расположены по разные стороны от главной диагонали симметрично друг другу. Матрица называется симметричной, если все симметричные элементы попарно равны.

Транспонированная матрица

Матрица A* называется транспонированной относительно A, если a*ik = aki, то есть симметричные элементы меняются местами. Зрительно это можно представить, как поворот матрицы вокруг главной диагонали. Строки при этом становятся столбцами, а столбцы – строками.

Единичная матрица

Матрица E, составленная из координат векторов канонического базиса, называется единичной. На главной диагонали у нее стоят единицы, остальные элементы равны нулю. Линейный оператор, соответствующий единичной матрице, также называется единичным. Он любой вектор переводит в себя:

E x = x.

Произведение матриц

Возьмем два линейных оператора

A = и В =

Рассмотрим последовательное действие этих операторов на произвольный вектор x:

y = Ax, z = By.

Легко проверить, что вектор z является линейной функцией от вектора x. Действительно, однородность и аддитивность выполняются. Обозначая этот оператор буквой C, запишем:

z = Cx = By = BAx,

C = BA.

Оператор C принято называть произведением операторов B и A. Рассмотрим, как вычислить его матрицу. Пусть cik – элементы этой матрицы. Тогда координаты вектора z:

zi = Σk cik xk.

По индексу k здесь производится суммирование k = 1, …, n. С другой стороны

zi = Σj bij yj = Σj bij Σk ajk xk.

Сравнивая коэффициенты при xk, получим

cik = Σj bij ajk .

Таким образом, для вычисления элемента cik матрицы C, находящегося на пересечении i-той строки и k-того столбца, нужно скалярно умножить i-ую строку матрицы B на k-тый столбец матрицы A. Это правило распространяется и на другие случаи, в частности, на умножение прямоугольных матриц. Нужно, конечно, чтобы длина строки первой матрицы была равна длине столбца второй матрицы. Число строк произведения при этом такое же, как у первой матрицы, а число столбцов – как у второй.

Действие линейного оператора A на вектор можно представить, как умножение матриц, если векторы x и y считать матрицами с одним столбцом. При умножении каждой строки матрицы A на матрицу x получается элемент матрицы y.

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

Вырожденная матрица, оператор

Оператор и его матрица называются вырожденными, если столбцы матрицы линейно зависимы. Вырожденный оператор переводит n – мерное пространство в подпространство меньшей размерности.

Обратная матрица, оператор

Укажем без доказательства, что для невырожденного оператора y = Ax обратное преобразование x = By является линейным оператором. При этом x = By = BAx. Это означает, что BA = E. Оператор B называется обратным к A и обозначается A-1. Заметим, что y = Ax = ABy = y, так что оператор A также является обратным к B: AB = E.

1.1.7Определитель

Определителем называется числовая кососимметрическая линейная функция от n векторов n – мерного пространства. Обозначение d = Det(a1, a2, , an) соответствует употребляемому иногда термину "детерминант". Координаты векторов можно записать в виде столбцов матрицы и говорить об определителе матрицы. Линейность подразумевается по каждому аргументу. Кососимметричность означает, что при перемене местами двух векторов определитель меняет знак. Например, Det(a2 , a1, , an) = - Det(a1 , a2, , an).

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

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

Det(e1 , e2 , , en ) = Det(E ) = 1.

Это даёт возможность вычислить произвольный определитель

d = Det(a1 , a2 , , an ).

Подставим в определитель a1 = a11 e1 + a21 e2 + …+ an1 en . Используя свойство линейности по первому аргументу, получим:

d = a11 Det(e1 , a2 , , an ) + a21 Det(e2 , a2 , , an ) + … + an1 Det(en , a2 , , an).

Это выражение состоит из n слагаемых. Каждое слагаемое представляет собой произведение одной из координат первого столбца матрицы на определитель, у которого на месте первого аргумента вместо произвольного вектора a1 стоит один из векторов базиса.

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

Если среди этих векторов есть одинаковые, то определитель равен нулю. По этой причине большая часть слагаемых пропадает. У оставшихся членов определитель содержит все векторы канонического базиса, но, вообще говоря, не в естественном порядке. Переставляя векторы местами, мы можем превратить порядок в естественный. Определитель при этом становится равным единице. Слагаемое тем самым превращается в произведение n коэффициентов матрицы и берется со знаком + или – в зависимости от того было ли число перестановок четным или нечетным.

Полученное таким образом выражение очень громоздко и им практически не пользуются, кроме случаев вычисления определителей низкого порядка. Приведем формулы для n = 1, 2, 3.

A =

Det(A ) = a11

A =

Det(A ) = a11 a22 a21 a12

A =

Det(A ) = a11 a22 a33 + a21 a32 a13 + a12 a23 a31

a31 a22 a13 a21 a12 a33 a32 a23 a11

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

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

Det(a1 + k a2, a2 ,, an ) = Det(a1 , a2 ,, an ) + k Det(a2 , a2 ,, an ) = Det(a1 , a2 ,, an).

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

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



Похожие документы:

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

    Решение
    ... ее решение. Для этого присвоим некоторой переменной М матрицу значений коэффициентов при неизвестных ... на рис. (). l Рис. Пример решения системы линейных уравнений 4. Решение системы линейных алгебраических уравнений методом ... 26 12 27 13 28 14 29 15 30
  2. Решение системы уравнений (1)

    Решение
    ... х0; у0) - решение системы уравнений 1) -2; ... , опреде­лите значения х, при которых у < 2. 1) ... № задания 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 4 3 2 1 4 2 3 3 2 1 4 2 2 3 4 2 3 3 2 3 2 4 2 3 2 2 3 2 2 1 3 1 3 4 4 4 3 1 2 4 2 4 4 1 2 3 3 3 1 4 ...
  3. Решение системы уравнений (2)

    Решение
    ... … Ответ: 8 5. Если х1, х2, х3 – решение системы уравнений то 6х1 + 4х2 + х3 ... равен… Ответ: 1 Задание 3 Наименьшее значение , при котором абсцисса точки перегиба графика ... … Ответ: 4 4. Интеграл равен … Ответ: 14 5. Интеграл равен … Ответ: 18 6. Интеграл ...
  4. Решение системы совокупность n чисел

    Решение
    ... A. J=1,2,..., n. Формулы вычисления неизвестных - решения системы - носят название формул Крамера. Используется ... и масштаб остаются неизменными. 14. Уравнение линии на плоскости ... Функция ограниченная при x® a.Функция ограниченная при x® Ґ.Теорема. Если ...
  5. Решение по делу №05-02/197Ж-14 Резолютивная часть решения объявлена 09 июля 2014 года

    Решение
    ... 05-02/197Ж-14 Резолютивная часть решения объявлена 09 июля ... (при необходимости). При этом данным пунктом Закона о контрактной системе предусмотрен ... извещение №01712000001914001718) необоснованной. Настоящее решение может быть обжаловано в судебном ...

Другие похожие документы..