Lanczos法を利用したTSVD法の積分方程式への応用

全文

(1)Vol.2018-HPC-163 No.4 2018/2/28. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. Lanczos ๏Λར༻ͨ͠ TSVD ๏ͷੵ෼ํఔࣜ΁ͷԠ༻ ลɹԕ1,a). ໺ࣉɹོ2,b). ֓ཁɿຊߘ͸ɼඇద੾໰୊ͷதͰ୅දతͳୈҰछ Fredholm ੵ෼ํఔࣜͷ਺஋ղ๏ʹ͍ͭͯߟ͑Δɽ࠷ॳ ʹɼ͜ͷΑ͏ͳ໰୊ͷղ๏ʹ༻͍ΒΕΔ TSVD ͷ‫ج‬ຊతͳߟ͑ํʹ͍ͭͯड़΂Δɽ࣍ʹɼTSVD ๏Λ࣮ߦ Ͱ͖Δ‫ݹ‬యతͳ Lanczos ๏ʹ͍ͭͯɼॏΈ෇͖ͷੵ෼ެࣜΛ༻͍ͨ৔߹ʹਫ਼౓ྑۙ͘ࣅղΛ‫͖Ͱࢉܭ‬Δम ਖ਼๏ΛఏҊ͢Δɽ࠷‫ʹޙ‬ɼ਺஋࣮‫ݧ‬Λ௨ͯ͠ɼఏҊख๏ͷ༗ޮੑʹ͍ͭͯड़΂Δɽ. Lanczos type iteration to TSVD method for solving Fredholm integral equation of the first kind Yuan Bian1,a). Takashi Nodera2,b). Abstract: Recently, a method called TSVD (Truncated Singular Value Decomposition) has been attracting some attention for solving Fredholm integral equation of the first kind. Solving a discretized this problem is a well-known ill-conditioned problem. This paper explains why the TSVD method performs well when solving Fredholm integral equations of the first kind, and proposes a new kind of TSVD method, which is combined with the Lanczos method. The results of numerical experiments are shown to confirm the effectiveness of our proposed method.. ͕ඇৗʹେ͖͍ɽͭ·Γɼ‫ࢉܭ‬தͰඍখͳ‫Ͱࠩޡ‬΋݁Ռʹ. 1. ͸͡Ίʹ. ലେͳӨ‫ڹ‬Λ༩͑Δ͜ͱʹͳΔɽΏ͑ʹɼͨͩ x = A−1 b. ୈҰछ Fredholm ੵ෼ํఔࣜ: b K(x, y)f (y)dy = g(x). Ͱ‫͢ࢉܭ‬Ε͹େ͖ͳ‫͕ࠩޡ‬ੜ͡ΔՄೳੑ͕ߴ͘ɼਫ਼౓ͷΑ ͍ղΛ‫ٻ‬ΊΔͷ͸ͦΕ΄Ͳ༰қͰ͸ͳ͍ɽͦΕղܾࡦͷ 1. (1). a. Λߟ͑Δɽͨͩ͠ɼੵ෼֩ͱ‫ݺ‬͹ΕΔ 2 ม਺ؔ਺ K(x, y) ͱӈଆͷؔ਺ g(x) ͕‫ط‬஌Ͱɼf (y) ͸‫ٻ‬Ί͍ͨະ஌ؔ਺Ͱ ͋Δɽ͜͜Ͱɼf, g ∈ L2 [a, b]ɼK ∈ L2 ([a, b] × [a, b]) Λߟ ͑Δɽ͜ͷํఔࣜΛ཭ࢄԽ͢͠Δͱɼ࣍ͷΑ͏ͳઢ‫ํܗ‬ఔ ͕ಘΒΕΔɽ. Ax = b,. A∈R. , b∈R. n. (2). Ұछ Fredholm ੵ෼ํఔࣜΛ཭ࢄԽͯ͠ಘΒΕΔͷͰ୅ද తͳѱ৚݅໰୊ͱͳΓɼ΄ͱΜͲͷ৔߹Ͱߦྻ A ͷ৚݅਺. 2 a) b). TSVD(Truncated Singular Value Decomposition) ๏͸ɼ ѱ৚݅ͷઢ‫ํܗ‬ఔࣜ (2) Λղͨ͘ΊʹΑ͘࢖ΘΕΔख๏ͷ. 1 ͭͰ͋Δɽಛʹඇద੾ͳ໰୊ͱͯ͠஌ΒΕ͍ͯΔୈҰछ Fredholm ੵ෼ํఔࣜͷ਺஋ղͱͯ͠༗ޮͰ͋Δɽ ߦྻ A ͷ৚݅਺͕ඇৗʹେ͖͍৔߹ɼ௨ৗɼߦྻ A ͕ ଟ਺ͷ 0 ʹ͍ۙಛҟ஋Λ࣋ͭ͜ͱ͕ଟ͍ɽͦͷͨΊɼͦΕ. n×n. ࣜ (2) ͸ɼ਺஋తʹ؆୯ʹղ͚ͦ͏ʹ‫͑ݟ‬Δ͕ɼ࣮ࡍɼୈ. 1. ͭ͸ɼTSVD ๏Λར༻͢Δ͜ͱͰ͋Δɽ. ‫ܚ‬ጯٛक़େֶେֶӃཧ޻ֶ‫ڀݚ‬Պ ˟ 223-8522 ԣ඿ࢢߓ๺۠೔٢ 3-14-1 ‫ܚ‬ጯٛक़େֶཧ޻ֶ෦ ˟ 223-8522 ɹԣ඿ࢢߓ๺۠೔٢ 3-14-1 [email protected] [email protected]. ⓒ 2018 Information Processing Society of Japan. ΒΛ௚઀ 0 ʹ͢Δ͜ͱʹΑΓ ɼ৚݅਺Λஶ͘͠‫ݮ‬গͤ͞ Δ͜ͱ͕Ͱ͖ɼਫ਼౓ͷΑ͍ղΛಘΔ͜ͱ͕‫ظ‬଴Ͱ͖Δͷ͕. TSVD ๏ͷ‫ج‬ຊతͳߟ͑ํͰ͋Δɽ۩ମతʹ‫͑ݴ‬͹ɼߦྻ A ͕࣍ͷΑ͏ͳಛҟ஋෼ղΛ࣋ͭͱ͢Δɽ A = U ΣV ∗ , Σ = diag{σ1 , σ2 , · · · , σn }. (3). ΋͠ σk+1 , · · · , σn ͕ 0 ʹ͍ۙಛҟ஋Ͱ͋Ε͹ɼͦΕΒΛ௚ ઀ 0 ʹ͢Δɽ͜ͷૢ࡞Ͱɼ‫ݩ‬ͷߦྻ A ͕࣍ͷΑ͏ʹͳΔɽ. Ak = U Σk V ∗ , Σk = diag{σ1 , σ2 , · · · , σk 0, · · · , 0} (4) 1.

(2) Vol.2018-HPC-163 No.4 2018/2/28. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ͜͜ͰɼAk ͕ਖ਼ଇߦྻͰͳ͍ͨΊɼਖ਼֬ͳղ͕ඞͣ͠΋ ଘࡏ͢Δͱ͸‫ݶ‬Βͳ͍ɽͦΕ‫ʹނ‬ɼ৽͍͠໰୊Λ࠷খೋ৐ ໰୊ͱͯ͠ղ͘ඞཁ͕͋Δɽ. ui = σi−1 Kvi. (10). ui ͷఆٛΑΓɼ಺ੵ ui , ui ͱ ui , uj ʢͨͩ͠ɼui = uj ʣ ͸ɼ࣍ͷΑ͏ʹ‫͖Ͱࢉܭ‬Δɽ. xk = argmin Ak x − b. (5). x. ui , ui = σi−1 Kvi , σi−1 Kvi = σi−2 vi , K∗ Kvi . ͜ͷ࠷খೋ৐໰୊Λղ͍ͯɼxk ͸࣍ͷࣜͰ༩͑ΒΕΔɽ. xk = V Σ−1 k U∗ b. (6). = σi−2 vi , σi2 vi = 1 ui , uj =. ߟ͑ํʹͦͷ··ैͬͯ‫͢ࢉܭ‬Δͱɼߦྻ A ͷ‫׬‬શͳಛҟ ஋෼ղ͕ඞཁͰ͋ΔͨΊɼे෼ͳ‫͕ؒ࣌ࢉܭ‬ඞཁͱͳΔɽ ͦΕ͚ͩͰͳ͘ɼ্‫ه‬ͷٞ࿦͚ͩͰɼxk ͕ x ʹ͍ۙɼଈ ͪɼಛҟ஋ͷ੾Γࣺͯͷૢ࡞͕ղʹ΋ͨΒ͢Ө‫͕ڹ‬খ͍͞. =. σi−2 vi , K∗ Kvj . = σi−2 vi , σi2 vj = 0. ‫ࢉܭ‬ͷ్தͰখ͍͞ಛҟ஋͕࢖ΘΕͳ͔ͬͨͨΊɼxk Λ ൺֱతਫ਼౓Α͘‫ٻ‬ΊΔ͜ͱ͕Ͱ͖Δɽ͔͠͠ɼTSVD ๏ͷ. (11). σi−1 Kvi , σi−1 Kvj . (12). ࣜ (11) ͱ (12) ΑΓɼ{ui }∞ i=1 ΋ਖ਼‫ن‬௚ަ‫ܥ‬Λͳ͢ɽ ࣍ʹɼK∗ ui Λߟ͑Δɽ. K∗ ui = K∗ σi−1 Kvi = σi−1 K∗ Kvi = σvi. (13). ࣜ (10) ͱࣜ (13) Λ߹Θͤͯɼ࣍ͷ͜ͱ͕Θ͔Δɽ. ͜ͱΛઆ໌͢Δͷ͸ࢸ೉ͷٕͰ͋Δɽ ຊߘͰ͸ͦͷΑ͏ͳ໰୊఺Λվળͯ͠ɼ·ͣ࿈ଓͷࢹ఺ ͔ΒɼୈҰछ Fredholm ੵ෼ํఔࣜͷͨΊͷ TSVD ๏Λಋ ग़͠ɼੵ෼ํఔࣜʹର͢Δ༗ޮੑʹ͍ͭͯड़΂Δɽ࣍ʹɼ ཭ࢄԽͨ͠໰୊ʹରͯ͠ɼLanczos ๏Λར༻ͨ͠ TSVD ๏ ΛఏҊ͢Δɽ࠷‫ʹޙ‬ɼ͍͔ͭ͘ͷ਺஋࣮‫ݧ‬Λ௨ͯ͠ɼఏҊ ख๏ͷ༗ޮੑΛ‫͢ূݕ‬Δɽ. Kvi = σi ui , K∗ ui = σi vi. (14). ࣜ (14) ΑΓɼσi ɼui ɼvi ͸ K ʹରͯ͠ɼߦྻͷಛҟ஋ͱಛ ҟϕΫτϧͱࣅͨΑ͏ͳ໾ׂͰ͋ΔɽͦΕΒΛ༻͍ͯɼؔ ਺ K(x, y) ͷߦྻͷಛҟ஋෼ղͱಉ༷ͳ΋ͷΛߟ͑Δɽ. vi ͷ ఆ ٛ Α Γ ɼK(x, y) ͸ vi ͱ ಺ ੵ Λ औ Ε Δ ͜ ͱ ͕ อ ূ ͞ Ε Δ ɽ‫ ʹ ނ‬ɼK(x, y) Λ y ͷ ؔ ਺ ͱ Έ ͳ ͤ ͹ ɼ. 2. ୈҰछ Fredholm ੵ෼ํఔࣜͷ TSVD ๏ ࣜ (1) Ͱ༩͑ΒΕͨੵ෼ํఔࣜΛߟ͑Δɽͦͷੵ෼Λؔ ਺ f ʹֻ͚Δ࡞༻ૉͱΈͳͤ͹ɼ࡞༻ૉͷ‫͖ॻͰࣜܗ‬௚͢. K(x, y) ∈ span{vi }∞ i=1 Ͱ͋ΔɽͦͷͨΊɼK(x, y) ʹର ͯ࣍͠ͷΑ͏ͳల։͕Ͱ͖Δɽ. K(x, y) =. ͜ͱ͕Ͱ͖Δɽ. Kf = g. =. (7). ͜͜Ͱɼ࡞༻ૉ K ͸࣍ͷΑ͏ͳ΋ͷͰ͋Δɽ b Kf (y) = K(x, y)f (y)dy. =. i=1 ∞ i=1 ∞ . K(x, y), vi (y)vi (y) (Kvi )vi (y) σi ui (x)vi (y). (15). i=1. (8). a. ∞ . ࣜ (15) ΑΓɼߦྻͷಛҟ஋෼ղͱྨࣅ͢Δؔ਺ K(x, y) ͷ. ͨͩ͠ɼK ∈ L2 ([a, b] × [a, b]) ΑΓɼK ͸ L2 [a, b] ͔Β. ಛҟ஋෼ղ͕ಘΒΕͨɽ࣍ʹɼ͜ͷ෼ղΛ༻͍ͯɼ‫ݩ‬ͷํ. L2 [a, b] ΁ͷ࡞༻ૉͰɼ༗քʢΏ͑ʹ࿈ଓʣઢ‫༻࡞ܕ‬ૉͰ͋. ఔࣜͷղΛߟ͑Δɽ. ∗. ΔɽͦͷͨΊɼਵ൐࡞༻ૉ K ͕ଘࡏ͢Δɽ·ͨɼK ͕ί ∗. ϯύΫτͰ͋Δ͜ͱ΋ূ໌Ͱ͖Δ [6]ɽΑͬͯɼK K ͕ࣗ ‫ݾ‬ਵ൐ͳ൒ਖ਼ఆ஋Ͱɼ͔ͭίϯύΫτͳ࡞༻ૉͰ͋Γɼ࣍. i = 1, 2, · · ·. ͏ʹͳΔɽ. . b. K(x, y)f (y)dy =. ࣜΛຬͨ͢‫ݻ‬༗஋ σi ͱ‫ݻ‬༗ؔ਺ vi ͕ଘࡏ͢Δɽ. K∗ Kvi = σi vi ,. ࣜ (15) Λ࠷ॳͷํఔࣜ (1) ʹ୅ೖ͢Δͱɼࠨଆ͕࣍ͷΑ. a. (9). =. ͞Βʹɼ{vi }∞ i=1 ͸ਖ਼‫ن‬௚ަ‫ܥ‬Λͳ͢ɽ·ͨɼඇྵͷ σi ͷ ‫͕਺ݸ‬༗‫ݸݶ‬ɼ·ͨ͸Մࢉແ‫͋Ͱݸݶ‬Δ [5]ɽͦ͜Ͱɼ࠷. =. i=1 ∞ i=1 ∞ . b a. σi ui (x)vi (y)f (y)dy. σi ui (x). . b a. vi (y)f (y)dy. σi f, vi ui (x). (16). i=1. ॳʹɼඇྵͷ σi ͷ‫͕਺ݸ‬Մࢉແ‫͋Ͱݸݶ‬ΔͷΛԾఆ͢Δɽ ༗‫ݸݶ‬ͷ৔߹͸ຊઅͷ࠷‫͑ߟͰޙ‬Δ͜ͱʹ͢Δɽ. ∞ . ࣜ (16) ΑΓɼࣜ (1) ͷࠨଆ͕ਖ਼‫ن‬௚ަ‫{ ܥ‬ui }∞ i=1 ͷுΔۭ ؒʹೖ͍ͬͯΔɽͦͷͨΊɼӈଆͷؔ਺ g ͸೚ҙʹબͿ. 2.1 ඇྵͷ σi ͕Ճࢉແ‫͋Ͱݸݶ‬Δ৔߹ ∗. ࠷ॳʹɼK K ͷ 1 ͭͷ‫ݻ‬༗ϖΞ. (σi2 , vi ). ؔ਺ ui Λఆٛ͢Δɽ ⓒ 2018 Information Processing Society of Japan. ͜ͱ͕Ͱ͖ͳ͍ɽղ͕ଘࡏ͢Δ͜ͱΛอূ͢ΔͨΊɼg ΋ ʹରͯ͠ɼ࣍ͷ. {ui }∞ i=1 ͷுΔۭؒͷதʹͳ͍ͱ͍͚ͳ͍ɽ͜ͷ࣌ɼg ͸࣍ ͷల։Λ࣋ͭɽ. 2.

(3) Vol.2018-HPC-163 No.4 2018/2/28. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report ∞ . g=. g, ui ui. (17). i=1. ࣜ (16) ͱࣜ (17) Λ߹ΘͤΔͱɼํఔࣜ (1) ͸࣍ࣜͷΑ͏ ʹͳΔɽ ∞ . N ΑΓେ͖͍ i ʹରͯ͠ɼui Λ KK∗ ͷ 0 ʹରԠ͢Δ‫ݻ‬༗ ؔ਺ͱ͢Ε͹ɼ͕࣍ࣜ੒Γཱͭ͜ͱʹͳΔɽ. K∗ Kvi = KK∗ ui = 0, i > N. ΑͬͯɼKvi , Kvi = K∗ Kvi , vi = 0 Ͱ͋Δ͜ͱΑΓɼ. σi f, vi ui (x) =. i=1. ∞ . g, ui ui (x). (18). i=1. ࣜ (18) ͷ྆ଆͷ ui ͷ܎਺Λൺֱ͢Δͱɼ࣍ͷ͜ͱ͕Θ ͔Δɽ. Kvi = 0 Ͱ͋Δ͜ͱ͕Θ͔Δɽಉ༷ʹɼK∗ ui = 0 ΋੒Γཱ ͭɽͭ·Γɼi > N ͷ࣌ɼࣜ (14) ͕੒ΓཱͪɼͦΕʹଓ͘ ಉ͡ཧ࿦Ͱɼࣜ (19) ͷલ൒ σi f, vi = g, ui ͕ಘΒΕΔɽ ͜ͷ࣌ɼࣜ (20) ͷΑ͏ͳ‫ Ͱ਺ڃ‬f Λද͢͜ͱ͕Ͱ͖ͳ͍ ͕ɼi > N ͷ i ʹରͯ͠ɼf, vi ͸೚ҙͷ஋ΛऔΔ͜ͱ͕. σi f, vi = g, ui . Ͱ͖Δɽͭ·Γɼ͜ͷ৔߹͸ɼղ͕ҰҙͰ͸ͳ͍ɽ͔͠͠ɼ. σi−1 g, ui . ⇒ f, vi =. (19). ࠷‫ʹޙ‬ɼf ͷ vi ʹΑͬͯల։͢Δͱɼσi ɼui ɼvi Λ༻͍ͯ. i > N Ͱ͋Δ i ʹରͯ͠ɼf, vi = 0 ʹ͢Δͱɼ1 ͭͷղ f ͕ಘΒΕΔɽ࣮͸ɼ͜Ε͕ Kf = g Λຬͨ͢ f ͷதͰϊϧ Ϝ࠷খͷ΋ͷͰ͋Δɽ. ղ f Λදࣔ͢Δ͜ͱ͕Ͱ͖Δɽ. f =. ∞ . f = fN =. f, vi vi. ⇒f =. ∞ i=1. (20). i→∞. σi−1 g, ui vi ͕ൃࢄ͢ΔΑ͏ʹ‫͑ݟ‬ΔͷͰɼશମͷ‫਺ڃ‬΋ൃ 2. ࢄ͢ΔΑ͏ʹ‫͑ݟ‬Δɽ͔͠͠ɼK(x, y) ∈ L ([a, b] × [a, b]) 2. 2. Ͱ͋Ε͹ɼ࡞༻ૉ K : L [a, b] → L [a, b] Λఆٛ͢Δ͜ ͱ͕Ͱ͖ɼ೚ҙͷ g ∈ R(K)(⊂ L2 [a, b]) ʹରͯ͠ɼඞͣ. Kf = g, f ∈ L2 [a, b] ͱͳΔ‫ ૾ݪ‬f ͕ଘࡏ͢Δɽ্‫ه‬ΑΓ f ͸ɼࣜ (20) ͷΑ͏ͳ‫ܗ‬Λ࣋ͭɽf ͕ L2 [a, b] ͷ‫͋Ͱݩ‬Δ͜ ͱΑΓɼL2 ϊϧϜ͕༗‫ͳݶ‬ͷͰɼࣜ (20) ͷӈଆͷ‫͕਺ڃ‬ ඞͣऩଋ͢Δɽ ࣜ (20) ͷӈଆ͕ऩଋ͢Δ࣌ɼ͢ͳΘͪɼk → ∞ ͷ࣌ɼ ‫਺ڃ‬ͷલ k ߲Λআ͍ͨୈ k + 1 ߲͔Βͷ૯࿨͕ 0 ʹऩଋ͢ Δɽͭ·Γɼ͕࣍ࣜ੒Γཱͭɽ. lim. σi−1 g, ui vi = 0. (24). ͱ͕Θ͔Δɽ. 3. Lanczos ๏ + TSVD ๏ ࠷΋ࣗવͳ཭ࢄԽͷߟ͑ํ͸ɼRiemann ࿨Λ࢖ͬͯࣜ. (1) Λ཭ࢄԽ͠ɼઢ‫ํܗ‬ఔࣜ Ax = b ΛಘΔ͜ͱͰ͋Δɽ࿈ ଓͷ৔߹ͱಉ༷ʹߦྻ A ͷಛҟ஋ͱಛҟϕΫτϧΛ༻͍ͯ ղ x ͷۙࣅ஋Λ‫ٻ‬ΊΔɽ. xk =. k i=1. σi−1 (u∗i b)v i. (25). ͜͜Ͱɼ΄ΜͷҰ෦ͷಛҟ஋ͱಛҟϕΫτϧ͕ඞཁͳͷͰɼ ߦྻ A ʹରͯ͠ Lanczos ๏͕࢖͑Δɽଟ਺ͷಛҟ஋͕ 0 ʹ ͍ۙͷͰɼҰൠʹ Lanczos ๏ͷऩଋ͕଎͍ɽ. ˆ1 ͱ u ˆ 1 = Aˆ Lanczos ๏͸೚ҙͷϕΫτϧ v v 1 /Aˆ v1 ͔ Β࢝·Γɼ࣍ͷ൓෮Λߦ͏͜ͱʹͳΔ [3]ɽ. (21). k+1. ˆ i−1 αi−1 , ˆ i = A∗ u ˆ i−1 − v v î = v ˆ i /βi−1 ˆ v i = βi−1 , v. ͦͷͨΊɼࣜ (21) ͷӈଆͷલ k ߲ͷ૯࿨͚ͩͰɼ໨ඪͷղ. f ͷۙࣅ஋ fk Λ‫ٻ‬ΊΔ͜ͱ͕Ͱ͖Δɽ f ≈ fk =. σi−1 g, ui vi. ैͬͯɼࣜ (24) Λ͜ͷղͷۙࣅͱͯ͠࢖͏͜ͱ͕Ͱ͖Δ͜. σi−1 g, ui vi. લड़ͷ lim σi = 0 ΑΓɼࣜ (20) ͷӈଆͷ‫਺ڃ‬ͷ߲. ∞ . N i=1. i=1. k→∞. (23). k i=1. σi−1 g, ui vi. î = u ˆ i /αi ˆ ui = αi , u (22). ͜ΕͰɼ୅਺త TSVD ๏ͱಉ༷ʹɼখ͍͞ಛҟ஋Λ੾Γ ࣺͯΔ͜ͱʹΑͬͯɼ࿈ଓͷ৔߹ͷղ f ͷۙࣅ஋Λಛҟ஋ ͱಛҟϕΫτϧͰද͢͜ͱ͕Ͱ͖ͨɽ. 2.2 ඇྵͷ σi ͕༗‫͋Ͱݸݶ‬Δ৔߹ ඇྵͷ σi ͕༗‫͋Ͱݸݶ‬Δ৔߹ɼͦͷ‫਺ݸ‬Λ N ∈ N ͱ ͢Ε͹ɼi > N Ͱ͋Δ͢΂ͯͷ σi = 0 ʹͳΔɽ͜ͷ࣌ɼ. i = 1, 2, · · · , N ʹରͯ͠ɼui ͸લड़ͱಉ༷ʹఆٛͰ͖ɼ KK∗ ͷ σi ʹରԠ͢Δ‫ݻ‬༗ؔ਺Ͱ͋Δ͜ͱʹ͸มΘΒͳ͍ɽ ⓒ 2018 Information Processing Society of Japan. (26). ˆ i−1 βi−1 ˆ i = Aˆ vi − u u. ͨͩ͠ɼ͋Δ βm ͕े෼খ͍͞৔߹ʹऩଋͨ͠ͱ൑ఆ͢Δɽ ͜ͷ࣌ɼ͕࣍ࣜಘΒΕΔɽ . A∗ A. . . Vˆm ˆm U. =. . Vˆm ˆm U. Hm. . Tm. ͨͩ͠ɼTm ͸֤ αi ͱ βi ͔ΒͳΔ࣍ͷΑ͏ͳ̎ॏର֯ߦ ྻͰɼHm ͸ Tm ͷసஔͰ͋Δɽ ⎞ ⎛ α1 β1 ⎟ ⎜ ⎟ ⎜ .. ⎟ ⎜ . α 2 ∗ ⎟ , H m = Tm Tm = ⎜ ⎟ ⎜ . .. β ⎟ ⎜ m−1 ⎠ ⎝ αm. (27). 3.

(4) Vol.2018-HPC-163 No.4 2018/2/28. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ௨ৗɼm ͸େ͖͘ͳ͍ͷͰɼTm ͷҰൠͷ SVDɿ Tm = ˆm U, Vm = U Σm V ∗ ͕؆୯ʹ‫͖Ͱࢉܭ‬Δɽ࠷‫ ʹޙ‬Um = U ˆ Vm V ͱ͓͚͹ɼߦྻ A ͷ෦෼తͳ SVD ͕ಘΒΕΔɽ. AVm = Um Σm. (28). ͜͜ͰಘΒΕͨಛҟ஋ͱಛҟϕΫτϧΛ༻͍ͯɼࣜ (25) Ͱ ղ x ͷۙࣅ஋Λ‫ٻ‬ΊΔ͜ͱ͕Ͱ͖Δɽ. ˆ i−1 − v ˆ i−1 αi−1 , ˆ i = A∗ W u v î = v ˆ i /βi−1 ˆ v i W = βi−1 , v î = u ˆ i /αi ˆ ui W = αi , u î ͱ v ˆ i ͸ɼຊ౰ʹਖ਼‫ن‬௚ަͳϕ ࣜ (32) Ͱੜ੒͞ΕΔ֤ u Ϋτϧͳͷ͔Λ͜͜Ͱ͔֬ΊΔɽ͋ΔεςοϓͰ͢Ͱʹಘ. ͔͠͠ɼRiemann ࿨͸ੵ෼ͷ཭ࢄԽ๏ͱͯ͠ਫ਼౓͕ͦ Ε΄ͲΑ͍Θ͚Ͱ͸ͳ͍ɽΑΓਫ਼౓ͷ͍͍ੵ෼ެࣜ͸ɼ. Boole ͷެ͕ࣜߟ͑ΒΕΔɽBoole ͷެࣜΑΓ x0 ͱ xn ͷ ؒͷؔ਺ f (x) ͷੵ෼͸ɼ2 ͭͷ୺఺ͱͦͷؒͷ n ౳෼఺. ˆ2, · · · , v î ͱ u ˆ 2, · · · , u ˆ i ͕ਖ਼‫ن‬௚ަͰ͋Δ ˆ1, v ˆ 1, u ΒΕͨ v ˆ i+1 ͕ಘΒΕΔɽ ͱԾఆ͢Δɽͦͯ͠ɼࣜ (32) Ͱ৽͍͠ v ˆ i+1 ͱ v ˆ j ͷ಺ੵΛऔΔͱɼ j = 1, 2, · · · , i − 2 ʹରͯ͠ɼv ࣍ࣜͷΑ͏ʹͳΔɽ. x1 , x2 , · · · , xn−1 ʹ͓͚Δؔ਺஋Λ࢖͑͹࣍ͷΑ͏ͳۙࣅ ͕Ͱ͖Δɽͨͩ͠ɼh = 1/nɽ b n 2 h f (x)dx ≈ wi f (xi ) 45 i=0 a ⎧ ⎪ 7 (i = 0 or n) ⎪ ⎪ ⎪ ⎨ 14 (i = 4k) wi = ⎪ 32 (i = 4k + 1 or 4k + 3) ⎪ ⎪ ⎪ ⎩ 12 (i = 4k + 2). ˆ j W = v ˆ ∗j W v ˆ i+1 = ˆ v i+1 , v. 1 1 ˆ j )∗ W u ˆ i = (αj u î ˆ ∗j + βj−1 u ˆ ∗j−1 )W u (AW v βi βi =0 (33) ˆ i+1 ͱ v ˆ i ͷ಺ੵΛऔΔͱ࣍ʹͳΔɽ ·ͨɼv (29). î = v ˆ ∗i W v ˆ i+1 = ˆ v i+1 , v. 1 ˆ i )∗ W u ˆ i − αi ) ((AW v βi 1 ˆ i − αi ) ˆ ∗i + βi−1 u ˆ ∗i−1 )W u = ((αi u βi 1 = (αi − αi ) = 0 βi. K(xi , yj )(i, j = 0, 1, · · · , n) ͔ΒͳΔߦྻͱ͢Δɽͦͯ͠ɼ ॏΈΛද͢ߦྻ W Λ࣍ͷΑ͏ʹఆٛ͢Δɽ. (30). ͜͜Ͱɼੵ෼࡞༻ૉ K ͷ཭ࢄԽ͸ AW Ͱද͢͜ͱ͕Ͱ͖ɼ ಘΒΕͨઢ‫ํܕ‬ఔࣜ͸ AW x = b ͱͳΔɽ Ұ‫ݟ‬ɼ͜ͷΞϧΰϦζϜͷߦྻ A ͷͱ͜Ζʹ AW Λ୅ ೖͯ͠‫͚͍ͯ͠ࢉܭ‬͹ྑ͍Α͏ʹ‫͑ݟ‬Δ͕ɼͦΕΛ࣮ࡍʹ ࣮ߦͯ͠ΈΔͱɼ๬·͍݁͠ՌΛಘΔ͜ͱ͕Ͱ͖ͳ͔ͬͨɽ ͦͷཧ༝͸ɼ΋͠ߦྻ AW ΛલͷΞϧΰϦζϜʹ௚઀୅ ೖ͢Δͱɼ࡞༻ૉ K∗ ʹରԠ͢Δߦྻ͕ (AW )∗ = W A∗ ʹ. a. (34). ˆ i+1 ͕લͷ͢΂ ࣜ (33) ͱࣜ (34) ΑΓɼ৽͘͠ಘΒΕͨ v ˆ j (j ≤ i) ͱ௚ަ͢Δɽಉ༷ͳٞ࿦Ͱɼu ˆ i+1 ͸͢΂ͯ ͯͷ v ˆ j (j ≤ i) ͱ௚ަ͢Δ͜ͱ͕Θ͔Δɽैͬͯɼࣜ (33) Ͱ ͷu n. n. ੜ੒͞ΕΔ {ˆ ui }i=1 ͱ {ˆ v i }i=1 ͸ɼͦΕͧΕਖ਼‫ن‬௚ަྻʹ ͳΔɽ લͱಉ͡ɼ͋Δ βi ͕े෼খ͍࣌͞ɼΞϧΰϦζϜ͕ऩ ଋͨ͠ͱ൑ఆ͢Δɽऩଋͨ࣌͠ɼલͱࣅͨΑ͏ͳ͕ࣜಘΒ ΕΔɽ . A∗ W AW. (31). 1 ∗ ˆ i − αi v ˆ W (A∗ W u î) v βi i. =. ·ͣɼx0 = y0 = a, xn = yn = b ͱ͠ɼߦྻ A Λ֤. ͳΔɽ͔͠͠ɼK∗ ͸ɼ࣍ࣜͰ‫ه‬ड़Ͱ͖Δɽ b ∗ K g= K(x, y)g(x)dx. 1 ∗ ˆ i − αi v ˆ W (A∗ W u î) v βi j. =. ͨͩ͠ɼk ∈ N. ࣜ (29) ʹैͬͯ཭ࢄԽΛߦ͏ͳΒɼ. W = diag{w0 , w1 , · · · , wn }. (32). î − u ˆ i−1 βi−1 ˆ i = AW v u. . . Vˆm ˆm U. =. . Vˆm ˆm U. Hm. . Tm. ͨͩ͠ɼTm ͱ Hm ͸લड़ͱಉ͡΋ͷͰ͋Δɽ. K∗ ʹରԠ͢Δߦྻ͸ A∗ W ʹͳΔ͸ͣͰ͋ΔɽAW ͕ର. ࣍͸લड़ͱಉ͡ Tm ͷ௨ৗͷಛҟ஋෼ղ Tm = U Σm V ∗ ˆm U, Vm = Vˆm V ͱஔ͘ͱɼ্‫ه‬ͷؔ Λ‫ͯ͠ࢉܭ‬ɼUm = U. শͰ͸ͳ͍‫ݶ‬Γɼ྆ํ͕Ұக͠ͳ͍ɽͦͷͨΊɼ͜͜Ͱໃ. ܎ࣜΛར༻ͯ͠ɼ͕࣍ࣜಘΒΕΔɽ. ‫ʹނ‬ɼ΋ࣜ͠ (31) ͷੵ෼ެࣜͰ཭ࢄԽΛߦ͏ͱɼ࡞༻ૉ. ६͕ੜ͡Δɽ ͜ͷ໰୊Λղܾ͢ΔͨΊʹɼLanczos ๏ͷमਖ਼Λߟ͑Δɽ ·ͣɼੵ෼ެࣜʹରԠͰ͖Δ W Ͱఆ·Δ಺ੵͱϊϧϜΛɼ. = Vˆm V Σm U ∗ U = Vm Σm ˆ m Tm V AW Vm = AW Vˆm V = U. ࣍ͷΑ͏ʹఆٛ͢Δɽ. u, vW = u∗ W v,. ˆm U = Vˆm T ∗ U A∗ W U m = A ∗ W U m. ||u||W =. u, u,. ∀u, v ∈ Rn. ͜ͷ৽͍͠಺ੵͱϊϧϜͷಋೖʹΑͬͯɼLanczos ๏ͷ൓. ˆ 1 /AW v ˆ 1 W ͔Β࢝ ˆ1 ͱ u ˆ 1 = AW v ෮͸೚ҙͷϕΫτϧ v. ˆ m U Σm V ∗ V = U m Σ m = U ∗ ˆm U = U ∗ U = I ˆ∗ WU Um W Um = U ∗ U m. Vm∗ W Vm = V ∗ Vˆm∗ W Vˆm V = V ∗ V = I. ·Γɼຖճͷ൓෮͸࣍ͷΑ͏ʹͳΔɽ. ैͬͯɼ͜͜ͰಘΒΕͨ Um , Vm , Σm ͸͔֬ʹ W ʹಋ͔. ⓒ 2018 Information Processing Society of Japan. 4.

(5) Vol.2018-HPC-163 No.4 2018/2/28. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. . ΕΔ಺ੵͱϊϧϜͷҙຯͰߦྻ A ͷಛҟϕΫτϧͱಛҟ஋. sin(xy)f (y)dy =. ͔ΒͳΔߦྻͰ͋ΔɽಛʹɼલͷΑ͏ʹ‫ʹ͍ޓ‬ໃ६͢Δ͜ ͱ͕ͳ͍ɽ࢒Γ͸ࣜ (25) ʹԊͬͯۙࣅ஋Λ‫ٻ‬ΊΕ͹Α͍ɽ. 1 0. sin x − x cos x x2. ͨͩ͠ɼਅͷղ͸ f (y) = y Ͱ͋Δɽ. W ʹಋ͔ΕΔ಺ੵͱϊϧϜʹΑͬͯɼLanczos ൓෮Λमਖ਼. લͷྫ୊ͱಉ͡ɼ2 ͭͷํ๏Ͱ཭ࢄԽΛߦ͍ɼ‫ݹ‬యతͳ. ͯ͠ɼࣜ (29) ͳͲͷੵ෼ެࣜΛར༻ͯ͠཭ࢄԽͨ͠໰୊Λ. Lanczs ๏ͱमਖ਼൛ͷ࣮ߦ݁ՌΛௐ΂ͨɽͨͩ͠ɼࠓճͷӈ. ͏·͘ղ͚͹Α͍ɽ. ଆͷؔ਺ g(x) ͷ෼฼͕ x2 Ͱ͋ΔͨΊɼb0 = g(0) Λ௚઀. 4. ਺஋࣮‫ݧ‬. ‫͢ࢉܭ‬Δ͜ͱ͕Ͱ͖ͳ͍ͷͰɼ࣍ͷΑ͏ʹ b0 Λ 0 ʹ͓͚ Δ g(x) ͷ‫ͨ͠ࢉܭ͍͓ͯͱݶۃ‬ɽ. ਺஋࣮‫ݧ‬͸࣍ͷΑ͏ͳ‫ͨͬߦͰڥ؀ࢉܭ‬ɽ. b0 = lim. OS: Windows 10 Home(64-bit)ɼ. x→0. CPU: Intel Core i7-6700HQ CPU @ 2.60GHzɼ Memory: 16.0GBɼ. ྫ୊ 2 ͷ࣮ߦ݁ՌΛද 2 ʹ‫ه‬ड़ͨ͠ɽ·ͨɼ2 ͭͷํ๏ Ͱ‫ٻ‬Ίͨ݁Ռʹ‫·ؚ‬ΕΔ‫ࠩޡ‬͸ਤ 3 ʹࣔͨ͠ɽྫ୊ 1 ͱಉ. Program Language: MATLAB R2016aɽ. ༷ʹɼमਖ਼ͨ͠ Lanczos ๏͸ಉ͘͡Β͍ͷ࣌ؒͰ௨ৗͷ 3 ഒҎ্ͷਫ਼౓͕ಘΒΕͨɽ. 4.1 ྫ୊ 1 ࣍ͷੵ෼ํఔࣜΛߟ͑Δɽ 1 ex+1 − 1 exy f (y)dy = x+1 0. 4.3 ྫ୊ 3. ͨͩ͠ɼਅͷղ͸ f (y) = ey Ͱ͋Δɽ ͜͜Ͱ࢖͏ॏΈΛද͢ߦྻ W ͸ࣜ (30) Ͱఆٛ͞Εͨ΋ ͷΛ࢖͏ɽn = 2048, h = 1/n ͱ͢ΔͱɼA ͱ b ͸ҎԼͷ Α͏ʹͳΔɽ. ࣍ͷํఔࣜΛߟ͑Δɽ 1 5x2 − 5x + 3 (x − y)2 f (y)dy = 15 0 ͨͩ͠ɼਅͷղ͸ f (y) = 16y 2 − 16y + 3 Ͱ͋Δɽ. 2 ͭͷ‫ࠩޡࢉܭ‬ͷ݁ՌΛਤ 3 ʹࣔͨ͠ɽ࣍ʹ‫ؒ࣌ࢉܭ‬ͷ ൺֱΛද 3 ʹ‫ه‬ड़ͨ͠ɽࠓճͷ৔߹ɼ‫ͨͬ·ٻ‬ಛҟ஋ͷ‫ݸ‬. xi = yi = ih, i = 0, 1, · · · , n ⎛ e x 0 y0 e x 0 y 1 · · · e x 0 yn ⎜ xy ⎜ e 1 0 e x 1 y 1 · · · e x 1 yn ⎜ A = ⎜ .. .. .. ⎜ . . . ··· ⎝ x n y0 x n y1 x n yn e e ··· e b = (b0 , b1 , · · · , bn )∗ , bi =. sin x − x cos x x sin x sin x = lim =0 = lim x→0 x→0 2 x2 2x. ਺͕গͳͯ͘ɼ‫ݹ‬యతͳ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬͸લͷ. ⎞. ྫ୊ͱͦΕ΄ͲมΘΒͳ͍͕ɼ࢒ࠩͷখ͍͞ղΛಘΔ͜ͱ. ⎟ ⎟ ⎟ ⎟ ⎟ ⎠. exi +1 − 1 , xi + 1. ʹࣦഊͨ͠ɽҰํɼमਖ਼ͨ͠ Lanczos ๏Λར༻͢Δͱɼ࢒ ͕ࠩґવͱͯ͠খ͍͚ͩ͞Ͱͳ͘ɼ΄΅‫׬‬શʹਅͷղͱҰ க͢Δ‫ࢉܭ‬ղ͕ಘΒΕͨɽ. i = 0, 1, · · · , n. ͜ΕҎ߱ͷྫ୊΋ಉ͡Α͏ͳํ๏Ͱ཭ࢄԽΛߦ͏΋ͷͱ. ࢀߟจ‫ݙ‬ [1]. ͢Δɽ લઅͰड़΂ͨ‫ݹ‬యతͳ Lanczos ๏Λద༻ͨ͠ΞϧΰϦζ Ϝͱमਖ਼ͨ͠ Lanczos Λద༻ͨ͠ΞϧΰϦζϜΛͦΕͧ. [2]. Ε࣮ߦͯ͠ɼ࣮ߦ݁Ռ͸ද 1 ʹࣔͨ͠ɽ·ͨɼ֤ yi ʹ͓ ͚Δ‫ ࠩޡ‬e(yi ) = |fexact (yi ) − fnum (yi )| Λਤ 1 ʹϓϩοτ ͨ͠ɽ ද 1 ͱਤ 1 ͔Βɼ‫ݹ‬యతͳ Lanczos ๏ʹ͓͍ͯ΋ɼf (y) =. [3] [4]. y. e ͷ͖Ε͍ͳ‫͕ܗ‬ಘΒΕͨͱ͸͍͑ɼࡉ͔͘‫ࠩޡ‬Λ‫͠ࢉܭ‬ ͯΈΔͱɼਫ਼౓͕ͦΜͳʹ͍͍ͱ͸‫͍͕͍ͨݴ‬ɽͦΕ͸ൺ ֱతʹ‫͕ࠩޡ‬େ͖͍ Riemann ࿨Ͱ཭ࢄԽ͔ͨ͠ΒͰ͋Δɽ ҰํɼBoole ͷެࣜΛར༻ͨ͠मਖ਼൛ͷ Lanczos ͸ɼ‫ݹ‬య తͳ Lanczos ๏ʹൺ΂ͯ 3 ഒҎ্ͷਫ਼౓Λ࣮‫ͨ͠ݱ‬ɽn ͱ. [5] [6]. Silvia Noschese, Lothar Reichel, “A modified truncated singular value decomposition method for discrete illposed problems,” Numer. Linear Algebra Appl. 2014; 21: pp. 813–822. Robert Craig Schmidt, “The numerical solution of linear first kind Fredholm integral eqnarrays using an iterative method,” Iowa State University Digital Repository. 1987; pp. 73–81. Lloyd N. Trefethen, “Numerical Linear Algebra,” SIAM. 2007; pp. 414–415. Hong du, “Approximate solution of the Fredholm integral eqnarray of the first kind in a reproducing kernel Hilbert space,ʡɹ An International Journal of Rapid Publication 2008: 21, pp. 617–623. Martin Hanke,“A Taste of Inverse Problems Basic Theory and Examples,” SIAM. 2017; pp. 12-13,130–132. Paul Garrett: “Compact operators, Hilbert-Schmidt operators,” March 2012. pp. 2–3.. m, k ͷ஋͕ಛʹେ͖͘ͳ͍ͨΊɼ2 ͭͷํ๏ͱ΋࣮ߦ࣌ؒ ͕͔ͳΓ୹ͯ͘ɼແࢹͰ͖Δ΄ͲͰ͋Δɽ. 4.2 ྫ୊ 2 ࣍ͷํఔࣜΛߟ͑Δɽ ⓒ 2018 Information Processing Society of Japan. 5.

(6) Vol.2018-HPC-163 No.4 2018/2/28. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ද 1: ྫ୊ 1 ͷ࣮ߦ݁Ռͷൺֱ m. k. ࢒ࠩ. ɹ૬ର‫ࠩޡ‬. ࣮ߦ࣌ؒ (sec). ‫ݹ‬యతͳ Lanczos ๏ɹ. 10. 7. 2.5300 × 10−15. 2.7100 × 10−3. 0.2331s. मਖ਼ Lanczos ๏. 10. 6. 8.9763 × 10−16. 3.3327 × 10−10. 0.2030s. ද 2: ྫ୊ 2 ͷ࣮ߦ݁Ռͷൺֱ m. k. ࢒ࠩ. ɹ૬ର‫ࠩޡ‬. ࣮ߦ࣌ؒ (sec). ‫ݹ‬యతͳ Lanczos ๏ɹ. 7. 4. 9.5246 × 10−14. 2.5202 × 10−3. 0.1953s. मਖ਼ Lanczos ๏. 7. 4. 1.4434 × 10−14. 2.9982 × 10−10. 0.1667s. ද 3: ྫ୊ 3 ͷ࣮ߦ݁Ռͷൺֱ m. k. ࢒ࠩ. ɹ૬ର‫ࠩޡ‬. ࣮ߦ࣌ؒ (sec). ‫ݹ‬యతͳ Lanczos ๏ɹ. 2. 2. 3.2057 × 10−4. 1.8213 × 10−3. 0.1175s. मਖ਼ Lanczos ๏. 2. 2. 2.3977 × 10−15. 1.2275 × 10−15. 0.0766s. 2.5. 0.035 0.03. ×10-9. 2. 0.025 1.5 0.02 1. e(y). e(y). 0.015 0.01. 0.5. 0.005. 0. 0 -0.5. -0.005 -0.01. 0. 0.1. 0.2. 0.3. 0.4. 0.5. 0.6. 0.7. 0.8. 0.9. -1. 1. 0. 0.1. 0.2. 0.3. 0.4. 0.5. 0.6. 0.7. 0.8. 0.9. 1. y. y. (a) ‫ݹ‬యతͳ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬. (b) मਖ਼ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬. ਤ 1: ྫ୊ 1 ͷ Lanczos ๏ʹΑΔղͷ‫ࠩޡࢉܭ‬ͷ݁Ռ 9. ×10. -3. ×10. 8. -10. 8 6 7 4. 6. e(y). e(y). 5 2. 4 0. 3 2. -2 1 0. 0. 0.1. 0.2. 0.3. 0.4. 0.5. 0.6. 0.7. 0.8. 0.9. -4. 1. 0. 0.1. 0.2. 0.3. 0.4. y. 0.5. 0.6. 0.7. 0.8. 0.9. 1. y. (a) ‫ݹ‬యతͳ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬. (b) मਖ਼ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬. ਤ 2: ྫ୊ 2 ͷ Lanczos ๏ʹΑΔղͷ‫ࠩޡࢉܭ‬ͷ݁Ռ 4. ×10-3 8. ×10-15. 6. 3. 4. 2. 2 1. e(y). e(y). 0 0. -2 -4. -1. -6 -2 -8 -3 -4. -10. 0. 0.1. 0.2. 0.3. 0.4. 0.5. 0.6. 0.7. 0.8. 0.9. 1. y. (a) ‫ݹ‬యతͳ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬. -12. 0. 0.1. 0.2. 0.3. 0.4. 0.5. 0.6. 0.7. 0.8. 0.9. 1. y. (b) मਖ਼ Lanczos ๏ʹΑΔղͷ‫ࠩޡ‬. ਤ 3: ྫ୊ 3 ͷ Lanczos ๏ʹΑΔղͷ‫ࠩޡࢉܭ‬ͷ݁Ռ. ⓒ 2018 Information Processing Society of Japan. 6.

(7)