Интерполяционные полиномы Лагранжа: теория и применение
Lagrange polynomial
Интерполяционный многочлен Лагранжа: уникальный полином для аппроксимации данных. История, формула, применение в численном анализе, криптографии и кодировании.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Полиномы, используемые для интерполяции
Polynomials used for interpolation
В численном анализе интерполирующий полином Лагранжа — это единственный полином наименьшей степени, который интерполирует заданный набор данных. Для заданного набора координатных пар (xᵢ, yᵢ) точки xᵢ называются узлами, а yᵢ — значениями. Полином Лагранжа имеет степень n-1 и принимает каждое значение в соответствующем узле.
In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data. Given a data set of coordinate pairs with the are called nodes and the are called values. The Lagrange polynomial has degree and assumes each value at the corresponding node,
Хотя метод назван в честь Жозефа Луи Лагранжа, опубликовавшего его в 1795 году, он был впервые открыт в 1779 году Эдвардом Уорингом. Он также является прямым следствием формулы, опубликованной Леонардом Эйлером в 1783 году. Области применения полиномов Лагранжа включают метод Ньютона-Котса численного интегрирования, схему секретного распределения Шамира в криптографии и коррекцию ошибок Рида-Соломона в теории кодирования. Для равноотстоящих узлов интерполяция Лагранжа подвержена феномену Рунге, проявляющемуся в больших колебаниях.
Although named after Joseph Louis Lagrange, who published it in 1795, the method was first discovered in 1779 by Edward Waring. It is also an easy consequence of a formula published in 1783 by Leonhard Euler. Uses of Lagrange polynomials include the Newton–Cotes method of numerical integration, Shamir's secret sharing scheme in cryptography, and Reed–Solomon error correction in coding theory. For equispaced nodes, Lagrange interpolation is susceptible to Runge's phenomenon of large oscillation.
Перспектива из линейной алгебры
Решение задачи интерполяции приводит к задаче линейной алгебры, сводящейся к инверсии матрицы. Используя стандартный базис из мономов для нашего интерполяционного многочлена, необходимо инвертировать матрицу Вандермонда для нахождения коэффициентов . Выбирая более удобный базис – базис Лагранжа – мы получаем единичную матрицу, которая является своей собственной обратной: базис Лагранжа автоматически инвертирует аналог матрицы Вандермонда. Эта конструкция аналогична китайской теореме об остатках. Вместо проверки остатков целых чисел по модулю простых чисел, мы проверяем остатки от деления многочленов на линейные множители. Более того, при большом порядке многочлена, быстрое преобразование Фурье может быть использовано для нахождения коэффициентов интерполированного многочлена.
Solving an interpolation problem leads to a problem in linear algebra amounting to inversion of a matrix. Using a standard monomial basis for our interpolation polynomial , we must invert the Vandermonde matrix to solve for the coefficients of By choosing a better basis, the Lagrange basis, , we merely get the identity matrix, , which is its own inverse: the Lagrange basis automatically inverts the analog of the Vandermonde matrix. This construction is analogous to the Chinese remainder theorem. Instead of checking for remainders of integers modulo prime numbers, we are checking for remainders of polynomials when divided by linears. Furthermore, when the order is large, Fast Fourier transformation can be used to solve for the coefficients of the interpolated polynomial.
Определенные поля
Полином Лагранжа также может быть вычислен в конечных полях. Это находит применение в криптографии, например, в схеме разделения секрета Шамира.
The Lagrange polynomial can also be computed in finite fields. This has applications in cryptography, such as in Shamir's Secret Sharing scheme.