Extremal polynomials and methods of optimization of numerical algorithms

V. I. Lebedev

Sbornik. Mathematics, Tome 195 (2004) no. 10, pp. 1413-1459

Résumé

Chebyshëv–Markov–Bernstein–Szegö polynomials $C_n(x)$ extremal on $[-1,1]$ with weight functions $w(x)=(1+x)^\alpha(1- x)^\beta/\sqrt{S_l(x)}$ where $\alpha,\beta=0,\frac12$ and $S_l(x)=\prod_{k=1}^m(1-c_kT_{l_k}(x))>0$ are considered. A universal formula for their representation in trigonometric form is presented. Optimal distributions of the nodes of the weighted interpolation and explicit quadrature formulae of Gauss, Markov, Lobatto, and Rado types are obtained for integrals with weight $p(x)=w^2(x)(1-x^2)^{-1/2}$. The parameters of optimal Chebyshëv iterative methods reducing the error optimally by comparison with the initial error defined in another norm are determined. For each stage of the Fedorenko–Bakhvalov method iteration parameters are determined which take account of the results of the previous calculations. Chebyshëv filters with weight are constructed. Iterative methods of the solution of equations containing compact operators are studied.

Bibliographie

[1] Bakhvalov N. S., Kobelkov G. M., Zhidkov N. P., Chislennye metody, Fizmatlit, M.–SPb., 2000 | Zbl

[2] Pashkovskii S., Vychislitelnye primeneniya mnogochlenov i ryadov Chebyshëva, Nauka, M., 1983 | MR

[3] Lebedev V. I., Funktsionalnyi analiz i vychislitelnaya matematika, Fizmatlit, M., 2000

[4] Chebyshëv P. L., “O funktsiyakh, malo udalyayuschikhsya ot nulya pri nekotorykh velichinakh peremennykh”, Polnoe sobranie sochinenii, t. 3, GITTL, M.–L., 1948, 108–120

[5] Markov A. A., “Lektsii o funktsiyakh, naimenee uklonyayuschikhsya ot nulya”, Izbrannye trudy, OGIZ, M., 1948, 244–291 | MR

[6] Bernshtein S. N., “Ob odnom klasse ortogonalnykh mnogochlenov”, Sobranie sochinenii, t. 1, Izd-vo AN SSSR, M., 1952, 452–465

[7] Bernshtein S. N., “O mnogochlenakh, ortogonalnykh na konechnom otrezke”, Sobranie sochinenii, t. 2, Izd-vo AN SSSR, M., 1954, 7–106

[8] Szegö G., “Über die Entwicrlung eine willkürlichen Funktion nach den Poynomen eines Orthogonalsystems”, Math. Z., 12 (1921), 64–94

[9] Segë G., Ortogonalnye mnogochleny, GIFML, M., 1962

[10] Lebedev V. I., “O edinoi formule dlya fazovoi funktsii ekstremalnykh ChMBS-mnogochlenov 1–4 roda”, Dokl. RAN, 389:1 (2003), 23–26 | MR | Zbl

[11] Lebedev V. I., “ChMBS-mnogochleny i kvadraturnye formuly povyshennoi tochnosti dlya nekotorykh klassov integralov s zavisyaschimi ot parametrov vesovymi funktsiyami”, Dokl. RAN, 390:5 (2003), 590–594 | MR

[12] Lebedev V. I., “ChMBS-mnogochleny i algoritmy optimizatsii chebyshëvskikh iteratsionnykh metodov na klassakh nachalnykh oshibok”, Dokl. RAN, 393:3 (2003), 312–316

[13] Lebedev V. I., “Ekstremalnye ChMBS-mnogochleny 1–4 roda i metody optimizatsii vychislitelnykh algoritmov”, Trudy matem. in-ta im. N. I. Lobachevskogo, 20, Kazanskoe matem. obsch-vo, Kazan, 2003, 37–86

[14] Lebedev V. I., “Iteratsionnye metody resheniya lineinykh operatornykh uravnenii i mnogochleny, naimenee otklonyayuschiesya ot nulya”, Matematicheskii analiz i smezhnye voprosy matematiki, Nauka, Novosibirsk, 1978, 89–108

[15] Lebedev V. I., “Extremal polynomials with restrictions and optimal algorithms”, Advanced mathematics: computations and applications, NCC Publisher, Novosibirsk, 1995, 491–502 | MR

[16] Lebedev V. I., “A new method for determining the roots of polynomials of least deviation on a segment with weight and subject to additional conditions. Part I, Part II”, Russian J. Numer. Anal. Math. Modelling, 8:3 (1993), 195–222 | MR | Zbl

[17] Marchuk G. I., Lebedev V. I., Chislennye metody v teorii perenosa neitronov, Atomizdat, M., 1981 | MR

[18] Krein M. G., Nudelman A. A., Problema momentov Markova i ekstremalnye zadachi, Nauka, M., 1973 | MR

[19] Akhiezer N. I., Lektsii po teorii approksimatsii, Nauka, M., 1965 | MR

[20] Geronimus Ya. L., “O nekotorykh uravneniyakh v konechnykh raznostyakh i sootvetstvuyuschikh sistemakh ortogonalnykh polinomov”, Dokl. AN SSSR, 29 (1940), 536–538 | MR | Zbl

[21] Geronimus Ya. L., “O polozhitelnykh trigonometricheskikh polinomakh i garmonicheskikh funktsiyakh”, Dokl. AN SSSR, 51 (1946), 569–572 | MR | Zbl

[22] Geronimus Ya. L., “O nekotorykh uravneniyakh v konechnykh raznostyakh i sootvetstvuyuschikh sistemakh ortogonalnykh mnogochlenov”, Zapiski matem. otd. fiz.-matem. f-ta KhTU i Kharkovskogo matem. obschestva, XXV:4 (1957), 87–100

[23] Lebedev V. I., “O reshenii obratnykh zadach i trigonometricheskikh formakh dlya mnogochlenov Geronimusa”, Russian J. Num. Anal. Math. Modelling, 15:1 (2000), 73–93 | MR | Zbl

[24] Lebedev V. I., “Ob iteratsionnykh metodakh resheniya operatornykh uravnenii, spektr kotorykh lezhit na neskolkikh otrezkakh”, ZhVM i MF, 9:6 (1969), 1247–1253

[25] Lebedev V. I., “Chebyshev and optimals-in-mean iterative methods for problems with spectrum contained in two segments or incide lemniscates”, East-West. J. Numer. Math., 2:2 (1994), 107–127 | MR | Zbl

[26] Lebedev V. I., Zabelin V. V., “On one class of three-term iterative methods with Chebyshev parameters”, Sov. J. Numer. Anal. Math. Modelling, 5:4/5 (1990), 275–298 | MR | Zbl

[27] Natanson I. P., Konstruktivnaya teoriya funktsii, GITTL, M.–L., 1949

[28] Krylov V. I., Priblizhennoe vychislenie integralov, GIFML, M., 1959

[29] Mysovskikh I. P., Lektsii po metodam vychislenii, Izd-vo SPbGU, SPb., 1998

[30] Baburin O. V., Lebedev V. I., “O vychislenii integralov v smysle glavnogo znacheniya vesov i uzlov kvadraturnykh formul Gaussa”, ZhVM i MF, 5:3 (1965), 451–462 | MR

[31] Baburin O. V., Lebedev V. I., “O vychislenii tablits kornei i vesov polinomov Ermita i Lagerra dlya $n=1(1)101$”, ZhVM i MF, 7:4 (1967), 1021–1030 | MR | Zbl

[32] Lebedev V. I., “Algoritmy opredeleniya parametrov odnogo klassa kvadraturnykh formul”, Voprosy vychislitelnoi i prikladnoi matematiki, no. 51, Izd-vo AN Uzb.SSR, Tashkent, 1978, 44–51

[33] Lebedev V. I., “Kvadraturnye formuly po poverkhnosti vytyanutogo ellipsoida vrascheniya”, Kubaturnye formuly i ikh prilozheniya, Izd-vo Vost.-Sib. gos. tekh. un-ta, Ulan-Ude, 1997, 48–56

[34] Gradshtein I. S., Ryzhik I. M., Tablitsy integralov, summ, ryadov i proizvedenii, Nauka, M., 1971

[35] Nikolskii S. M., Kvadraturnye formuly, Nauka, M., 1988 | MR

[36] Dovgii S. A., Lifanov I. K., Metody resheniya integralnykh uravnenii, Naukova dumka, Kiev, 2002 | Zbl

[37] Bernshtein S. N., “Ob asimptoticheskom znachenii nailuchshego priblizheniya analiticheskikh funktsii”, Sobranie sochinenii, t. I, Izd-vo AN SSSR, M., 1952, 127–135

[38] Gavurin M. K., “Primenenie polinomov nailuchshego priblizheniya k uluchsheniyu skhodimosti iterativnykh protsessov”, UMN, 5:3 (1950), 156–160 | MR | Zbl

[39] Fedorenko R. P., Vvedenie v vychislitelnuyu fiziku, Izd-vo MFTI, M., 1994

[40] Shaidurov V. V., Mnogosetochnye metody konechnykh elementov, Nauka, M., 1989 | MR

[41] Tikhonov A. N., Arsenin V. Ya., Metody resheniya nekorrektnykh zadach, Nauka, M., 1986 | MR | Zbl

[42] Khemming R. V., Tsifrovye filtry, Nauka, M., 1987

[43] Wiliam H. R., “High-order low-pass implicit tangent filters for use in finite area calculations”, Monthly Weather Review, 116 (1988), 2132–2141 | 2.0.CO;2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[44] Lebedev V. I., “Yavnye raznostnye skhemy dlya resheniya zhestkikh zadach s kompleksnym ili razdelimym spektrom”, ZhVM i MF, 40:12 (2000), 1801–1812 | Zbl

[45] Lebedev V. I., “Extremal polynomials, pseudo-difference operators, and stable explicit schemes for the solution of stiff nonstationary problems of mathematical physics”, Proc. of the International Conference on Computational Mathematics, Part I, Novosibirsk, 2002, 60–63 | MR