Кіріспе
Интерполяция үшін қолданылатын полиномиалдар. Сандық талдауда Лагранж интерполяциялық полиномиалы – берілген деректер жиынтығын интерполяциялайтын ең төменгі дәрежедегі бірегей полиномиал. Егер деректер жиынтығы координаттық жұптармен берілсе, онда координаталар түйіндер деп, ал мәндер оларға сәйкес келетін шамалар деп аталады. Лагранж полиномиалының дәрежесі n-ге тең болады және ол әрбір түйінде тиісті шаманы қабылдайды.
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,
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.
Бұл әдіс 1795 жылы Жозеф Луи Лагранж жариялағанмен, алғаш рет 1779 жылы Эдвард Уоринг тапқан. Сонымен қатар, бұл 1783 жылы Леонхард Эйлер жариялаған формуланың логикалық салдары болып табылады. Лагранж полиномиалдары Ньютон-Котс сандық интеграциялау әдісінде, Шамирдің криптографиядағы құпия бөлісу схемасында және кодтау теориясындағы Рид-Соломон қатесін түзетуде қолданылады. Бір-бірінен тең арақашықтықта орналасқан түйіндер үшін Лагранж интерполяциясы Рунж құбылысына ұшырауы мүмкін, яғни үлкен амплитудалы тербелістерге бейім.
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,
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.
Сызықтық алгебрадан көзқарас
Интерполяциялық мәселені шешу сызықтық алгебрада матрицаны инверсиялауға келтіретін мәселеге әкеледі. Интерполяциялық полином үшін стандартты мономиалды негізді қолдану арқылы, біз Вандермонд матрицасын кері бұруымыз керек. Бірақ, жақсырақ негізді, Лагранж негізін таңдау арқылы, біз өзінің кері матрицасы болып табылатын бірлік матрицаны ғана аламыз: Лагранж негізі Вандермонд матрицасының аналогын автоматты түрде инверсиялайды. Бұл құрылым қытайлық қалдық теоремасына ұқсас. Жақын сандарға қатысты бүтін сандардың қалдықтарын тексерудің орнына, біз сызықтықтарға бөлгенде көпмүшелердің қалдықтарын тексереміз. Сонымен қатар, дәрежесі жоғары болған жағдайда, интерполяцияланған полиномның коэффициенттерін табу үшін жылдам Фурье түрлендіруін қолдануға болады.
Шекті өрістер
Лагранж полиномиалы шекті өрістерде де есептелуі мүмкін. Бұл криптографияда, мысалы, Шамирдің құпия бөлісу схемасында қолданыс табады.