Лекции по "Ценообразованию"

Лекция 1

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

1. О приближенных вычислениях

 Реальное проведение любых вычислений проводится над числами, которые задаются не только точно, но и приближенно. Например, запись 7/3 обозначает число, но записать его в виде десятичной дроби можно только приближенно. Если же вычисления проводятся на компьютере, то приближенно записывать приходится не только числа типа 7/3, но многие другие. В результате возникают ошибки, которые постепенно накапливаются и искажают результат.

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

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

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

2. Линейные замены переменных

Рассмотрим систему равенств [pic 1].

Здесь [pic 2], - числа, а [pic 3] - переменные; благодаря этим равенствам переменные [pic 4] линейно выражаются через переменные [pic 5]. Это и есть линейная замена переменных.

        Зашифруем ее в виде следующей таблицы:

Ясно, что по такой таблице можно однозначно восстановить записи, определяющие  замену переменных. Предположим, что элемент [pic 31]. Из заданных равенств, а точнее из равенства номер [pic 32], в этом случае можно выразить [pic 33] через [pic 34] и [pic 35]: