русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритмы линейной алгебры


Дата добавления: 2013-12-23; просмотров: 1174; Нарушение авторских прав


Проект

Задачи

Итоги

Подводя некоторые итоги, отметим, что полином можно задать тремя разными способами - его коэффициентами, корнями и точками, через которые проходит полином. Если заданы коэффициенты полинома, то за время, пропорциональное можно вычислить значения полинома в n+1 точках. Для вычисления значения полинома в одной точке применяется схема Горнера, выполняющая вычисления за линейное (пропорциональное n) время. Существует и обратное преобразование. Если заданы n+1 точки, через которые проходит полином, то алгоритм Лагранжа позволяет за время вычислить коэффициенты полинома. Задача получения коэффициентов полинома по точкам называется задачей интерполяции, а полином Лагранжа называется интерполяционным полиномом.

Если заданы корни, то можно получить два других представления. Рассмотренный нами алгоритм позволяет по корням полинома за время вычислить коэффициенты полинома. Алгоритм использует итеративную схему из n шагов, где на каждом шаге выполняется операция повышения степени, выполняемая за линейное время. Поскольку корни являются частным случаем задания множества точек, через которые проходит полином, то задание корней автоматически задает и представление полинома набором точек. Обратная задача - получение корней по коэффициентам или заданным точкам - так просто не решается. Точное ее решение существует для полиномов второй и третьей степени, но не в общем случае. Для нахождения корней приходится использовать приближенные итеративные методы, например, метод простой итерации или Ньютона.

Задание полинома его корнями является наиболее информативным. Если известны корни, то без труда выполняется свертка полиномов. Вычисление значения полинома в заданной точке выполняется за n умножений, не требуя применения схемы Горнера. Несколько сложнее выполняется операция сложения полиномов. К сожалению, на практике редко встречается ситуация, когда известны корни полинома, но такое бывает - алгоритм Лагранжа тому пример.



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

На практике полиномы чаще всего появляются при задании множества точек. Ситуация обычно такова. В результате экспериментов измеряются значения некоторой функции в ряде точек. Требуется предсказать, каково будет значение этой функции в других точках, в которых измерения не проводились. Если из теоретических соображений не известен вид функции, то чаще всего ее задают в виде полинома, проходящего через точки, полученные экспериментальным путем. В этой постановке задачу построения полинома и вычисления значений полинома в точках, не подлежащих измерениям, называют задачей интерполяции, а полином Лагранжа называют интерполяционным полиномом. Задача интерполяции корректно решается, когда новые точки, в которых проводятся вычисления, лежат внутри интервала, заданного измеренными точками. Полиномы плохо приспособлены для решения задачи экстраполяции, когда точки лежат вне интервала измерений, из-за быстрого роста значения полинома вне этого интервала. Чем выше степень полинома, тем быстрее его рост.

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

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

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

  • 28. Полином P(x) задан своими коэффициентами. Дан массив координат X. Вычислить, используя схему Горнера, массив значений полинома в точках .
  • 29. Полином P(x) задан своими корнями и старшим коэффициентом an. Дан массив координат X. Вычислить массив значений полинома в точках .
  • 30. (задача интерполяции) Полином P(x) задан координатами n+1 точек, через которые он проходит. Дан массив координат X. Вычислить массив значений полинома в точках .
  • 31. Полином P(x) задан своими корнями и старшим коэффициентом an. Вычислить коэффициенты полинома.
  • 32. (задача построения интерполяционного полинома Лагранжа) Полином P(x) задан координатами n+1 точек, через которые он проходит. Вычислить коэффициенты полинома.
  • 33. Полином P(x) задан своими коэффициентами. Дан массив чисел X. Построить полином Q(X), имеющий своими корнями числа из массива X и корни полинома P(x).
  • 34. Полином P(x) задан своими коэффициентами. Для полинома известны два его корня - x0 и xn. Построить полином Q(x), корни которого совпадают с корнями полинома P(x), за исключением корней x0 и xn.
  • 35. Полиномы P(x) и Q(x) заданы своими корнями и старшими коэффициентами. Вычислить коэффициенты суммы полиномов P(x) и Q(x).
  • 36. Полиномы P(x) и Q(x) заданы своими корнями и старшими коэффициентами. Вычислить коэффициенты произведения полиномов P(x) и Q(x).
  • 37. Полиномы P(x) и Q(x) заданы своими коэффициентами. Вычислить коэффициенты суммы полиномов P(x) и Q(x).
  • 38. Полиномы P(x) и Q(x) заданы своими коэффициентами. Вычислить коэффициенты произведения полиномов P(x) и Q(x).
  • 39. Полиномы P(x) и Q(x) заданы точками, через которые они проходят. Вычислить коэффициенты суммы полиномов P(x) и Q(x).
  • 40. Полиномы P(x) и Q(x) заданы точками, через которые они проходят. Вычислить коэффициенты произведения полиномов P(x) и Q(x).
  • 41. Полином P(x) задан своими коэффициентами. Определить интервал, если он существует, на котором полином имеет хотя бы один корень.
  • 42. Полином P(x) задан точками, через которые он проходит. Определить интервал, если он существует, на котором полином имеет хотя бы один корень.
  • 43. Для полинома P(x), заданного своими коэффициентами, известен интервал, на котором полином имеет хотя бы один корень. Найти корень с заданной точностью, используя схему дихотомии.
  • 44. Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить схему исследования интервала и дихотомии.
  • 45. Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить метод простой итерации.
  • 46. Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить метод Ньютона.
  • 47. Построить проект, включающий построение интерфейса пользователя и класса Polinom. Методы класса должны реализовать все алгоритмы, рассмотренные в этом разделе. Интерфейс пользователя должен позволять пользователю решать основные задачи, возникающие при работе с полиномами.

Матрицей называется набор чисел, состоящий из m строк и n столбцов. Для программиста матрица - это двумерный массив. Матрица называется квадратной, если m = n, и прямоугольной - в противном случае. Числа m и n определяют размерность матрицы. Над прямоугольными матрицами определены операции транспонирования, сложения, умножения.

Пусть A - матрица размерности m*n (из m строк и n столбцов) с элементами . Транспонированной матрицей B = AT называют матрицу размерности n*m, элементы которой . В транспонированной матрице строки исходной матрицы становятся столбцами.

Операция сложения определена над прямоугольными матрицами одинаковой размерности. Пусть A, B, C - прямоугольные матрицы размерности m*n. Тогда сумма матриц определяется естественным образом:

Операция умножения определена над прямоугольными матрицами, у которых число столбцов первого сомножителя равно числу строк второго сомножителя. Матрица произведения имеет число строк, равное числу строк первого сомножителя, и число столбцов, равное числу столбцов второго сомножителя. Пусть A - матрица размерности m*p, B - размерности p*n, тогда матрица C= A*B имеет размерность m*n. Элементы матрицы произведения определяются как сумма попарных произведений элементов строки первого сомножителя на элементы столбца второго сомножителя.

(6.7)

Умножение всегда определено для прямой и транспонированной матрицы. Если A - прямоугольная матрица размерности m*n, то всегда определена квадратная матрица B размерности m*m:

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



<== предыдущая лекция | следующая лекция ==>
Сложение и умножение полиномов | Квадратные матрицы


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.002 сек.