Файл: 1-5.docx

1. Источники и классификация погрешностей численного решения математических задач. Неустранимая погрешность, погрешность метода, вычислительная погрешность.

Причины возникновения:

1. Математическое описание задачи может быть не точным

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

3. При вводе и выводе исходных данных, а также при выполнении алгебраических вычислений и округление числа

Существуют типы погрешностей:

1. Неустранимая погрешность

Неустранимая погрешность разделяется на две части:

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

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

2. Погрешность метода

3. Вычислительная погрешность

Общая погрешность – суммарная погрешность

Нат. < цел <Рац( бесконеч. периодич. Дробь) <Иррац (бесконеч. непериодич. Дробь

Рац и Иррац – вещественные (действии)

Комплексные числа – пара вещественных

2. Вычислительные методы линейной алгебры. Методы решения СЛАУ.

1. формулировка задачи

A(mxn) – матрица

Однородная система – если вектор свободных членов равен нулевому вектору (если правая часть нулевая)

=

1. m<n

неопределенная.

Бесчисленноемн-во решений

2. m=n

   =

2 решения

=

3. m>n

переопределенная.несовместная

Смысл решения системы – переход от одного базиса к другому.

Методы решения делят на три группы

1)прямые методы

2)Итерационные методы

3)методы типа Монте-Карло (сотни алгоритмов. Зависит от особенностей С.У.)

Комплексные числа представляют в виде пары вещественных чисел.

Формы представления чисел в компьютере.

В компьютере числа представляются

• c фиксированной точкой

• c плавающей точкой

Представление чисел с фиксированной точкой: все числа в ЭВМ имеют модуль, меньший 1; число знаков после запятой фиксировано. Один байт отводится на знак числа, фиксированное число байтов отводится на целую часть и фиксированное число – на дробную часть.

a = ± a_{n ,} a_n-1 … a₀ а_-1 а_-2 … а_-m

где a_i – разряды, (a_na_n-1 … a₀) – целые, (а_-1 а_-2 … а_-m) – дроби

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

а = ± a_n рⁿ + … + a₁ p + a₀ p⁰ + a_-1 p^-1 + … + a_mp^m,

где р – целое, основание системы счисления, a_i –целые натуральные числа, такие что(0 ≤ a_i<p)

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

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

а = М р^s,

где М – мантисса (множитель, содержащий все цифры числа), p – основание системы счисления, s – порядок числа (целое число). Причем (р^-1 ≤│M│<1), то есть мантисса должна быть правильной дробью, у которой первая цифра после запятой отлична от нуля.

Выводы:

1. Диапазон представления чисел с плавающей точкой гораздо больше, чем с фиксированной, поэтому их используют чаще

2. Числа с фиксированной точкой обрабатываются быстрее, чем с плавающей

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

Если a - точное значение некоторой величины, а а^*- известное приближение к нему (значение с погрешностью), то

Δа =│а– а^*│ - абсолютная погрешность,

а = а^* + Δа

δ(а) = Δа / (│а│) = (│а – а^*│) / │а│ - относительная погрешность,

а = а^* · (1 ± δ(а))

Оценки погрешностей

1. «Оценка снизу» получается отбрасыванием младших разрядов (усечением числа)

2. «Оценка сверху» или округление – более точный способ

│а₁ - а│≥│а₂ - а│=>a= а₂

│а₁ - а│<│а₂ - а│=>a= а₁

Δа ≤ ½ (а₂ - а₁) = ½ ·10^-t

δ(а) = ½ 10^1-t

где t – количество использованных разрядов

2) Метод Гаусса (схема единственного деления) решения систем линейных алгебраических уравнений. Трудоемкость и рабочее поле метода.

На iом шагевыбираем элемент a_ii .Принимаем j = i.Обзовем его ведущим. Делим строку (вместе с iым элементом столбца свободных членов)с номером i на этот элемент. Умножаем строку (вместе с iым элементом столбца свободных членов)с номером i на a_i+ji.И вычитаем из i ой(преобразованной умножением) строки,строку с номером i+j.Строку с номером i+j заменяем на получившуюся строку,строка с номером i остается неизменной.J увеличиваем на 1.и так продолжаем до тех пор пока j≠n.Как только j=n ,делаем последнее преобразование, выходим из цикла и увеличиваем i на 1 .и так до тех пор пока i≠n

Трудоемкость и рабочее поле метода

Рабочее поле: ячеек памяти

Трудоемкость метода

Прямой ход [ВМО]

Обратный ход

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

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

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

Сложение:

a=x1+x2

x1=x1*+1, 1

x2=x2*+2, 2

даны 2 числа х1и х2 с точными значением х1* и х2* и погрешностями 1, 2

и их сумма a.

тогда a= (x1*+1)+ (x2*+2)=(x1*+x2*)+(1+2)=a*+

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

||12

Вычитание:

Вычитанию соответствует аналогичный случай, что и сложению, но неизвестно возрастет она или уменьшится

Умножение:

a=(x1*+1)(x2*+2)=x1*x2*+x1*2+x2*1+12=a*+ x1*2 +x2*1+12

Видно, что погрешность может увеличиваться, а может и уменьшиться.

|x1*|2+|x2*|+12, где 12 очень мало, а значит |x1*|2+|x2*|1

Деление:

a=x1/x2

=-a*+a=a-a*=x1 – x1* =x1*+1 – x1* = (x1*+1)x2* - (x2*+2)x1* =

x2 x2* x2*+2 x2* (x2+2)x2*

= x1*x2* +1x2* - x1*x2*-2x1* = 1x1* - 2x1*x2*1+x1*2

(x2*+)x2* (x2*+)x2* (x2*)²

(x2*)² - влияет на величину погрешности. Погрешность тем меньше, чем больше знаменатель.

Значит, при делении величина погрешности уменьшается при увеличении знаменателя.

Вычисление обратной матрицы (от числовой), вычисление определителя матрицы

A(λ)=A_nλⁿ+...+ A₁ λ+ A₀ – полиномиальная матрица

Det(A₁λ+ A₀)=0 (только для квадратных матриц)

Det(A-λE)=0

A¹A=AA^-1=E–определение обратной матрицы

A*B≠B*A

A^-1*

Трудоемкость вычисления А^-1

(по схеме единственного деления)

Прямой ход

Обратный ход

Общая трудоемкость

Эта трудоемкость определяется трудностью метода решения СЛАУ

Полиномиальная матрица - это матрица в которой каждый элемент одномерный или многомерный полином.

Одномерная полиноминальная матрица P степени p определяется как:

где A(i) определяется матрицей постоянных величин , и A(p) не равняется нулю.Таким образом полиномиальная матрица является матрицей эквивалентной полиному, в котором каждый элемент матрицы удовлетворяет определению полинома степени р

Например полиномиальная матрица размерностью 3х3, степени 2:

Свойства

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

Полиномиальные матрицы еще называют λ-матрицами.

A(λ)= A_n λⁿ + A₁ λ + A₀

A_i – полиномиальная матрица степени n,элементы которой это полиномы степени n; i=1,n

Например, если степень матрицы A будет равно 0 (степень полинома,n=0), то A(λ)= A₀

Если n=1,то A(λ)= A₁ λ + A₀ (обобщенная проблема собственных значений)

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

a¹₁₁ λ + a⁰₁₁; . . . a¹_1n λ + a⁰_1n

a¹_n1 λ + a⁰_n1; . . . a¹_nn λ + a⁰_nn = S₁ + S!= b_nλⁿ + . . .+ b₁λ + b₀

получим некий характеристический многочлен: b_n λⁿ + . . .+ b₁λ + b₀

Может ли полиномиальная матрица быть вырожденной зависит от λ. Надо определить при каких λ этот многочлен будет =0 :

b₁ (λ- λ₁)…( λ- λ_n)=0 ,где λ.. . . λ_n– собственные значения матрицы

если det(λ_i)=0 , то λ_i– собственные значения

частный случай такой матрицы:

A(λ)= A- λE (стандартная проблема собственных значений)

Определим собственные векторы:

A(λ_i) B_i =0 –правый собственный вектор i=1,n

S^T_iA(λ_i) =0 – левый собственный вектор

Метод Гаусса с выбором ведущих элементов

Недостатки

- Не универсальность.

- Низкая точность.

Устранение недостатков

Матрицу перестановок Р называют квадратной матрицей ,у которой в каждой строке и в каждом столбце только один элемент отличается от 0 и =1

Элементарной матрицей перестановки P_kt называется матрица, полученная из единичной матрицы перестановкой kой и t ой строк

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

Выбор ведущих элементов по столбцам.

i=1..n

i=2..n

i=n

Трудоемкость

При перестановке столбцов в матрице будет меняться порядок следования переменных в векторе Х

Выбор ведущих элементов по строкам

i=1..n

i=2..n

i=n

Метод гаусса с выбором ведущих элементов по матрице

i=1..n;j=1..n

i=2..n;j=2..n

i=n;j=1

Заключение

1. За счет выбора ведущих элементов – универсальность, точность

2. Трудоемкость

3. Сохраняется недостаток обусловленный отсутствием информации об изменении правой части системы в процессе приведения её матрицы к треугольному виду