Tài liệu Phép chiếu vuông góc và một số ứng dụng

  • Số trang: 47 |
  • Loại file: PDF |
  • Lượt xem: 40 |
  • Lượt tải: 0
youtubehot

Tham gia: 22/05/2016

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM HOÀNG THỊ LIỄU PHÉP CHIẾU VUÔNG GÓC VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM HOÀNG THỊ LIỄU PHÉP CHIẾU VUÔNG GÓC VÀ MỘT SỐ ỨNG DỤNG Chuyên ngành: Giải tích Mã số: 60.46.01 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH. LÊ DŨNG MƯU Thái Nguyên - năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Môc lôc Lêi nãi ®Çu 1 2 C¸c kh¸i niÖm c¬ b¶n. 4 1.1 TËp låi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Tæ hîp låi. . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 TËp a-phin, tËp låi ®a diÖn. . . . . . . . . . . . . . . . . 6 1.1.3 Nãn låi. . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Hµm låi. 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 PhÐp chiÕu lªn tËp låi ®ãng. 18 2.1 §Þnh nghÜa vµ tÝnh chÊt. . . . . . . . . . . . . . . . . . . . . . 18 2.2 H×nh chiÕu cña mét ®iÓm lªn mét sè tËp quen thuéc. . . . . . . 24 3 Mét sè øng dông cña phÐp chiÕu. 28 3.1 §Þnh lý t¸ch tËp låi. . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 D­íi vi ph©n . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Gi¶i bÊt ®¼ng thøc biÕn ph©n. . . . . . . . . . . . . . . . . . . 39 Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lêi nãi ®Çu Gi¶i tÝch låi lµ bé m«n c¬ b¶n cña gi¶i tÝch hiÖn ®¹i, nghiªn cøu vÒ tËp låi vµ hµm låi cïng nh÷ng vÊn ®Ò liªn quan. Bé m«n nµy cã vai trß quan träng trong nhiÒu lÜnh vùc kh¸c nhau cña to¸n häc øng dông, ®Æc biÖt lµ trong tèi ­u hãa, bÊt ®¼ng thøc biÕn ph©n, c¸c bµi to¸n c©n b»ng... Mét trong nh÷ng vÊn ®Ò quan träng cña gi¶i tÝch låi ®ã lµ phÐp chiÕu vu«ng gãc. §©y lµ mét c«ng cô s¾c bÐn vµ kh¸ ®¬n gi¶n ®Ó chøng minh nhiÒu ®Þnh lý quan träng nh­ §Þnh lý t¸ch, §Þnh lý xÊp xØ tËp låi, §Þnh lý vÒ tån t¹i nghiÖm cña BÊt ®¼ng thøc biÕn ph©n...Nh÷ng c¸ch chøng minh dùa vµo phÐp chiÕu th­êng mang tÝnh chÊt kiÕn thiÕt, gîi më ®Õn nhiÒu vÊn ®Ò kh¸c. Trong luËn v¨n nµy, chóng t«i tËp trung vµo viÖc tr×nh bµy ®Þnh nghÜa c¸c kh¸i niÖm, tÝnh chÊt cïng nh÷ng øng dông quan träng cña phÐp chiÕu. Dùa vµo ®ã, chóng t«i giíi thiÖu thuËt to¸n ®Ó t×m nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n. Gi¶i quyÕt ®­îc bµi to¸n bÊt ®¼ng thøc biÕn ph©n th× chóng ta cã thÓ ®­a ra lêi gi¶i cho rÊt nhiÒu vÊn ®Ò kh¸c. Bëi v× nhiÒu bµi to¸n trong tèi ­u hãa, ph­¬ng tr×nh vËt lý to¸n vµ nhiÒu vÊn ®Ò trong kinh tÕ, kü thuËt giao th«ng ®« thÞ...®Òu ®­îc m« t¶ d­íi d¹ng ®ã. §Ò tµi bao gåm 3 ch­¬ng. Trong Ch­¬ng 1, tr­íc hÕt chóng t«i tr×nh bµy mét sè kiÕn thøc c¬ së cña tËp låi vµ hµm låi. Chóng lµ nh÷ng c«ng cô c¬ b¶n nhÊt cho nh÷ng nghiªn cøu ®­îc tr×nh bµy trong luËn v¨n. Ch­¬ng 2 lµ mét ch­¬ng chÝnh cña luËn v¨n. Trong ch­¬ng nµy chóng t«i dµnh ®Ó nãi riªng vÒ kh¸i niÖm, tÝnh chÊt c¬ b¶n cña phÐp chiÕu. §Æc biÖt chóng t«i tr×nh bµy c«ng thøc x¸c ®Þnh h×nh chiÕu cña mét ®iÓm lªn siªu hép, h×nh cÇu vµ kh«ng gian con cña Rn . Trong qu¸ tr×nh nghiªn cøu vÒ phÐp chiÕu vu«ng gãc, chóng ta biÕt r»ng h×nh chiÕu vu«ng gãc cña mét ®iÓm lªn tËp låi ®ãng, kh¸c rçng trong Rn lu«n tån t¹i vµ duy nhÊt. Dùa vµo ®ã, chóng t«i ®Ò cËp ®Õn nh÷ng øng dông 2 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn cña nã. Cô thÓ chóng t«i tr×nh bµy øng dông cña phÐp chiÕu vu«ng gãc vµo c¸c vÊn ®Ò sau: Chøng minh c¸c ®Þnh lý t¸ch, chøng minh sù tån t¹i cña d­íi vi ph©n cña hµm låi, x©y dùng thuËt to¸n gi¶i bÊt ®¼ng thøc biÕn ph©n. Nh÷ng vÊn ®Ò nµy ®­îc tr×nh bµy chi tiÕt ë Ch­¬ng 3. LuËn v¨n ®­îc hoµn thµnh d­íi sù h­íng dÉn tËn t×nh cña GS. TSKH. Lª Dòng M­u. Nhê ThÇy, t«i ®· b­íc ®Çu lµm quen vµ say mª trong c«ng viÖc nghiªn cøu to¸n. Nh©n dÞp nµy, t«i xin bµy tá lßng biÕt ¬n s©u s¾c tíi ThÇy. §ång thêi t«i còng ch©n thµnh c¶m ¬n c¸c thÇy c« gi¸o trong khoa To¸n Tr­êng §¹i häc S­ ph¹m Th¸i Nguyªn - §¹i häc Th¸i Nguyªn, ViÖn to¸n häc ®· tËn t×nh gi¶ng d¹y gióp t«i n¾m ®­îc nh÷ng kiÕn thøc c¬ së vµ t¹o ®iÒu kiÖn thuËn lîi cho hoµn thµnh luËn v¨n nµy. T«i xin c¶m ¬n ng­êi th©n, ®ång nghiÖp, b¹n bÌ ®· cæ vò ®éng viªn t«i trong qu¸ tr×nh lµm luËn v¨n. Th¸i Nguyªn, Ngµy 28 th¸ng 09 n¨m 2009 Häc viªn Hoµng ThÞ LiÔu 3 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ch­¬ng 1 C¸c kh¸i niÖm c¬ b¶n. Trong ch­¬ng nµy, chóng t«i tr×nh bµy nh÷ng kh¸i niÖm c¬ b¶n trong gi¶i tÝch låi cïng víi nh÷ng tÝnh chÊt ®Æc tr­ng cña nã nh­ tËp låi, tËp a-phin, nãn låi, hµm låi... 1.1 TËp låi. Nh÷ng tËp hîp quen thuéc mµ chóng ta ®· biÕt nh­ kh«ng gian con, siªu ph¼ng... ®Òu lµ tËp låi. Kh¸i niÖm vÒ tËp låi cã mét vai trß quan träng trong gi¶i tÝch låi. Trong phÇn nµy chóng t«i tr×nh bµy ®Þnh nghÜa, tÝnh chÊt cña tËp låi, tËp a-phin, tËp låi ®a diÖn, nãn låi... 1.1.1 Tæ hîp låi. §Þnh nghÜa 1.1.1. • Mét ®­êng th¼ng c¸c ®iÓm (vÐct¬) nèi hai ®iÓm (vÐct¬) a vµ b trong Rn lµ tËp hîp tÊt c¶ x ∈ Rn cã d¹ng {x ∈ Rn | x = (1 − λ)a + λb, λ ∈ R}. • Mét ®o¹n th¼ng ®iÓm (vÐct¬) nèi hai ®iÓm (vÐct¬) a vµ b trong Rn lµ tËp hîp tÊt c¶ c¸c x ∈ Rn cã d¹ng {x ∈ Rn | x = (1 − λ)a + λb, 0 ≤ λ ≤ 1} . 4 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn §Þnh nghÜa 1.1.2. Mét tËp C ⊆ Rn ®­îc gäi lµ mét tËp låi nÕu C chøa mäi ®o¹n th¼ng ®i qua hai ®iÓm bÊt kú cña nã. Tøc lµ C låi khi vµ chØ khi ∀x, y ∈ C, ∀λ ∈ [0; 1] =⇒ λx + (1 − λ)y ∈ C. x lµ tæ hîp låi cña c¸c ®iÓm (vÐct¬)x1 , . . . , xk nÕu Ta nãi x= k X i i n λi x , x ∈ R , λi ≥ 0, ∀i = 1, . . . , k, k X i=1 λi = 1. i=1 ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.1). TËp MÖnh ®Ò 1.1.3. C ⊆ Rn lµ låi khi C lµ låi khi vµ chØ khi nã chøa mäi tæ hîp låi cña c¸c ®iÓm cña nã. Tøc lµ, vµ chØ khi ∀k ∈ N, ∀λ1 , . . . , λk > 0 : k X 1 k λi = 1, ∀x , . . . , x ∈ C ⇒ i=1 k X λi xi ∈ C. i=1 Chøng minh. §iÒu kiÖn ®ñ: Suy ra tõ ®Þnh nghÜa cña tËp låi øng víi §iÒu kiÖn cÇn: k = 2. Ta chøng minh b»ng ph­¬ng ph¸p quy n¹p theo sè ®iÓm. k = 1 : HiÓn nhiªn. k = 2 : §iÒu kiÖn cÇn chøng minh suy ra ngay tõ ®Þnh nghÜa cña tËp låi vµ tæ hîp låi. Gi¶ sö mÖnh ®Ò ®óng víi ThËt vËy, nÕu k − 1 ®iÓm, ta chøng minh nã ®óng víi k ®iÓm. x lµ tæ hîp låi cña k ®iÓm x1 , . . . , xk ∈ C, tøc lµ : x= k X i λi x , λi > 0, ∀i = 1, . . . , k, i=1 Gi¶ sö k X λi = 1. i=1 λk > 0, ®Æt : α = k−1 P λi . Khi ®ã 0 < α < 1 vµ i=1 x= k−1 X i=1 Do k−1 X λi i x + λk xk . λi x + λk x = α α i=1 i k λi > 0 ∀i = 1, . . . , k − 1 vµ α k−1 X λi =1 α i=1 5 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nªn theo gi¶ thiÕt quy n¹p th× ®iÓm k−1 X λi i x ∈ C. y= α i=1 Ta cã : x = αy + λk xk . Do α > 0, λk > 0 vµ α + λk = k P λi = 1 nªn i=1 x lµ tæ hîp låi cña y vµ xk ®Òu thuéc C . VËy x ∈ C. Tõ ®Þnh nghÜa cña tËp låi, ta suy ra líp c¸c tËp låi lµ ®ãng víi phÐp giao, phÐp céng ®¹i sè vµ phÐp nh©n tÝch Decastes. MÖnh ®Ò 1.1.4. trong Rn , C ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.2). NÕu lµ tËp låi trong A, B lµ c¸c tËp låi Rm th× c¸c tËp sau lµ låi A ∩ B = {x | x ∈ A, x ∈ B} , αA + βB = {x | x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R} , A × C = {x ∈ Rm+n | x = (a; c), a ∈ A, c ∈ C} . 1.1.2 TËp a-phin, tËp låi ®a diÖn. Trong gi¶i tÝch cæ ®iÓn, ta ®· lµm quen víi c¸c kh«ng gian con, c¸c siªu ph¼ng...§ã lµ c¸c tr­êng hîp riªng cña tËp a-phin ®­îc ®Þnh nghÜa nh­ sau: §Þnh nghÜa 1.1.5. Mét tËp C ®­îc gäi lµ tËp a-phin nÕu nã chøa mäi ®­êng th¼ng ®i qua hai ®iÓm bÊt kú cña nã. Tøc lµ : ∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C. NhËn xÐt 1.1.6. a) TËp a-phin lµ mét tr­êng hîp riªng cña tËp låi. b) Mäi siªu ph¼ng trong Rn ®Òu lµ tËp a-phin. MÖnh ®Ò d­íi ®©y cho ta thÊy tËp a-phin chÝnh lµ ¶nh tÞnh tiÕn cña mét kh«ng gian con. 6 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MÖnh ®Ò 1.1.7. khi vµ chØ khi gian con (xem [2], Ch­¬ng 1, MÖnh ®Ò 1.3). TËp M M = L+a víi L 6= ∅ lµ tËp a-phin lµ mét kh«ng gian con vµ a ∈ M. Kh«ng L ®­îc x¸c ®Þnh duy nhÊt. Chøng minh. §iÒu kiÖn cÇn: Khi ®ã VËy Gi¶ sö M lµ tËp a-phin vµ a ∈ M . L = M − a chøa 0 vµ lµ tËp a-phin. Do ®ã, L lµ mét kh«ng gian con. M = L + a. §iÒu kiÖn ®ñ: NÕu M = L + a víi a ∈ M , L lµ kh«ng gian con th× ∀x, y ∈ M, λ ∈ R, ta cã: (1 − λ)x + λy = a + (1 − λ)(x − a) + λ(y − a). Do x − a, y − a ∈ L vµ L lµ kh«ng gian con nªn (1 − λ)(x − a) + λ(y − a) ∈ L. =⇒ (1 − λ)x + λy ∈ M. VËy M lµ tËp a-phin. Kh«ng gian con L ë trªn lµ duy nhÊt. ThËt vËy, nÕu M = L + a vµ M = L0 + a0 , trong ®ã L, L0 lµ nh÷ng kh«ng gian con vµ a, a0 ∈ M th× L0 = M − a = L + a − a0 = L + (a − a0 ). Do a0 ∈ M = a + L nªn a0 − a ∈ L. =⇒ L0 = L + (a − a0 ) = L. Kh«ng gian con song víi tËp a-phin L trong mÖnh ®Ò trªn ®­îc gäi lµ M. §Þnh nghÜa 1.1.8. Thø nguyªn( víi tËp a-phin kh«ng gian con song M ®­îc gäi lµ hay chiÒu) cña kh«ng gian con thø nguyªn( hay chiÒu) cña L song song M vµ ®­îc ký hiÖu lµ dimM . §iÓm a ∈ Rn lµ tËp a- phin cã sè chiÒu b»ng 0 bëi v× kh«ng gian con song song víi M = {a} lµ L = {0}. 7 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MÖnh ®Ò 1.1.9. M ⊆ Rn (xem [2], Ch­¬ng 1, MÖnh ®Ò 1.4). BÊt kú mét tËp a- phin cã sè chiÒu r ®Òu cã d¹ng M = {x ∈ Rn | Ax = b} Trong ®ã: A lµ ma trËn cÊp (m × n), b ∈ Rm Ng­îc l¹i, mäi tËp hîp cã d¹ng (1.1) víi vµ (1.1) rank A = n − r. rank A = n − r ®Òu lµ tËp a-phin cã sè chiÒu lµ r. Chøng minh. §iÒu kiÖn cÇn: Gi¶ sö M lµ tËp a-phin cã sè chiÒu lµ r vµ M = L + a víi a ∈ M . VËy L = M − a lµ kh«ng gian con cã sè chiÒu lµ r. Theo ®¹i sè tuyÕn tÝnh kh«ng gian con r - chiÒu nµy cã d¹ng : L = {x | Ax = 0} trong ®ã A lµ ma trËn cÊp m × n vµ rank A = n − r. Tõ M = L + a suy ra M = {x | A(x − a) = 0} = {x | Ax = Aa = b} . §iÒu kiÖn ®ñ: NÕu M ®­îc cho bëi (1.1) víi a ∈ M , ta cã Aa = b, do ®ã M = {x | A(x − a) = 0} = a + L víi L = {x | Ax = 0} . Do rankA = n − r nªn L lµ kh«ng gian con cã sè chiÒu r. VËy dim M = r. §Þnh nghÜa 1.1.10. • Siªu ph¼ng trong kh«ng gian Rn lµ tËp hîp c¸c ®iÓm cã d¹ng {x ∈ Rn | ha, xi = α} trong ®ã : VÐct¬ a ∈ Rn \ {0} , α ∈ R. a ë trªn ®­îc gäi lµ vÐct¬ ph¸p tuyÕn cña siªu ph¼ng. •Nöa kh«ng gian ®ãng lµ mét tËp hîp cã d¹ng: {x | ha, xi ≤ α} , {x | ha, xi ≥ α} 8 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn trong ®ã : a ∈ Rn \ {0} , α ∈ R. • Nöa kh«ng gian më lµ mét tËp hîp cã d¹ng: {x | ha, xi > α} , {x | ha, xi < α} . trong ®ã : a ∈ Rn \ {0} , α ∈ R. Nh­ vËy mét siªu ph¼ng chia kh«ng gian ra lµm hai nöa kh«ng gian, mçi nöa kh«ng gian ë vÒ mét phÝa cña siªu ph¼ng. NÕu hai nöa kh«ng gian nµy ®ãng th× phÇn chung cña chóng chÝnh lµ siªu ph¼ng. §Þnh nghÜa 1.1.11. Mét tËp hîp ®­îc gäi lµ tËp låi ®a diÖn, nÕu nã lµ giao cña mét sè h÷u h¹n c¸c nöa kh«ng gian ®ãng. §Þnh nghÜa 1.1.12. tùa t¹i Cho x0 ∈ C. Ta nãi siªu ph¼ng ha, xi = α lµ siªu ph¼ng x0 nÕu ha, x0 i = α, ha, xi ≥ α, ∀x ∈ C.  Ta nãi H = x | ha, x − x0 i ≤ 0 lµ nöa kh«ng gian tùa cña C t¹i x0 . §Þnh nghÜa 1.1.13. TËp tËp a-phin nhá nhÊt chøa KH: aff C , gäi lµ bao a- phin cña C C. MÖnh ®Ò 1.1.14. C C ⊆ Rn , giao cña tÊt c¶ c¸c tËp a-phin chøa C lµ (xem [2], Ch­¬ng 3, MÖnh ®Ò 3.2 ). Bao a- phin cña tËp lµ tËp bao gåm tÊt c¶ c¸c ®iÓm cã d¹ng x = λ1 x1 + . . . + λk xk sao cho xi ∈ C, λ1 + . . . + λk = 1 vµ k ∈ N. Chøng minh. Gi¶ sö Cho M lµ tËp hîp c¸c ®iÓm cã d¹ng (1.2). x, y ∈ M. Theo ®Þnh nghÜa cña M ta cã: x= k X λi xi i=1 y= h X µj yj j=1 9 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (1.2) trong ®ã xi ∈ C, ∀i = 1, . . . , k; yj ∈ C, ∀j = 1, . . . , h vµ k X λi = i=1 Th× mçi h X µj = 1. j=1 α ∈ (0; 1), ta cã : z = (1 − α)x + αy = k X i (1 − α)λi x + i=1 Do k X (1 − α)λi + h X i=1 nªn h X µj y j . j=1 αµj = (1 − α) + α = 1 j=1 z = (1 − α)x + αy ∈ M. Tõ ®ã suy ra M lµ tËp a - phin , affC ⊂ M. k k P P MÆt kh¸c: DÔ dµng thÊy r»ng nÕu x = λi xi víi xi ∈ C, λi = 1 th× i=1 x ∈ affC. Do ®ã M ⊂ affC VËy M = affE. §Þnh nghÜa 1.1.15.  aff i=1 x1 , . . . , x k C¸c ®iÓm x1 , . . . , xk ®­îc gäi lµ ®éc lËp a-phin nÕu cã sè chiÒu lµ k, tøc lµ, nÕu c¸c vÐc t¬ x1 −xk , . . . , xk−1 −xk lµ ®éc lËp tuyÕn tÝnh. HÖ qu¶ 1.1.16. Bao låi a-phin trong Rn lµ tËp a-phin Mäi ®iÓm x∈M M cña tËp (k − 1)− chiÒu. cã thÓ biÓu diÔn duy nhÊt d­íi d¹ng : x= k X i λi x , i=1 1.1.3  k ®iÓm ®éc lËp a-phin x1 , . . . , xk k X λi = 1. i=1 Nãn låi. Trong tèi ­u hãa, bÊt ®¼ng thøc biÕn ph©n, lý thuyÕt trß ch¬i vµ nhiÒu bé m«n to¸n øng dông kh¸c, kh¸i niÖm vÒ nãn cã mét vai trß quan träng. §Þnh nghÜa 1.1.17. Mét tËp C ®­îc gäi lµ nãn nÕu ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C. 10 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Theo ®Þnh nghÜa, ta thÊy r»ng gèc täa ®é cã thÓ thuéc nãn hoÆc kh«ng thuéc nãn. DÜ nhiªn mét nãn kh«ng nhÊt thiÕt lµ mét tËp låi. VÝ dô C = {x ∈ R | x 6= 0} lµ mét nãn nh­ng kh«ng låi. Mét nãn ®­îc gäi lµ nãn nhän nÕu nã kh«ng chøa ®­êng th¼ng. Khi ®ã ta nãi 0 lµ ®Ønh cña nãn. Mét nãn ®­îc gäi lµ nãn låi nÕu nã ®ång thêi lµ mét tËp låi. NÕu nãn låi nµy l¹i lµ mét tËp låi ®a diÖn th× ta nãi nã lµ nãn låi ®a diÖn. (xem [2], Ch­¬ng 1, MÖnh ®Ò 1.6). Mét tËp MÖnh ®Ò 1.1.18. C lµ nãn låi khi vµ chØ khi nã cã c¸c tÝnh chÊt sau: (i) (ii) λC ⊆ C, ∀λ > 0, C + C ⊆ C. Chøng minh. C lµ mét nãn låi. Do C lµ mét nãn, nªn ta cã (i). 1 Do C lµ mét tËp låi nªn víi mäi x, y ∈ C th× (x + y) ∈ C . 2 VËy theo (i) ta cã x + y ∈ C §iÒu kiÖn cÇn: §iÒu kiÖn ®ñ: Gi¶ sö Gi¶ sö ta cã (i) vµ (ii). Tõ (i) suy ra ngay Tõ (i) suy ra VËy C lµ mét nãn. Gi¶ sö x, y ∈ C vµ λ ∈ [ 0, 1] . λx ∈ C vµ (1 − λ)y ∈ C . Theo (ii) cã λx + (1 − λ)y ∈ C . C lµ mét nãn låi. §Þnh nghÜa 1.1.19. Cho gäi lµ h­íng lïi xa cña theo h­íng C lµ mét tËp låi trong Rn . Mét vÐc t¬ y 6= 0 ®­îc C , nÕu mäi tia xuÊt ph¸t tõ mét ®iÓm bÊt kú cña C y ®Òu n»m trän trong C . Tøc lµ : y lµ h­íng lïi xa khi chØ khi x + λy ∈ C, ∀x ∈ C, ∀λ ≥ 0. TËp hîp cña tÊt c¶ c¸c h­íng lïi xa cña hîp nµy ®­îc gäi lµ nãn lïi xa cña C cïng víi ®iÓm gèc lµ re C . TËp C. 11 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn HiÓn nhiªn nÕu Chó ý 1.1.20. hái víi mäi C lµ mét tËp bÞ chÆn th× re C chØ gåm duy nhÊt ®iÓm gèc. NÕu C lµ tËp låi ®ãng th× trong ®Þnh nghÜa trªn, thay v× ®ßi x ∈ C , chØ cÇn ®ßi hái cho mét ®iÓm x ∈ C . MÖnh ®Ò 1.1.21. ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.7). Gi¶ sö låi låi ®ãng. Khi ®ã y lµ mét h­íng lïi xa cña C C lµ mét tËp khi chØ khi x + λy ∈ C, ∀λ ≥ 0 víi mét ®iÓm x nµo ®ã thuéc Chøng minh. Gi¶ sö C. x + λy ∈ C, ∀λ ≥ 0 víi x ∈ C . ThÕ th× víi ∀u ∈ C vµ ∀µ > 0, do C låi, ta cã xλ = cho µ µ (x + λy) + (1 − )u ∈ C. λ+µ λ+µ λ −→ ∞, do C ®ãng , ta thÊy u + µy ∈ C , víi mäi u ∈ C vµ µ > 0. Chó ý 1.1.22. VÝ dô 1.1.23. Trong tr­êng hîp Trong C kh«ng ®ãng, mÖnh ®Ò trªn kh«ng ®óng. R2 lÊy C = {x = (x1 , x2 ) | x1 > 0, x2 > 0} ∪ {0} . HiÓn nhiªn, vÐc t¬ y = (0, 1) cã tÝnh chÊt lµ mäi tia xuÊt ph¸t tõ mét ®iÓm 0 6= x ∈ C theo h­íng nµy ®Òu n»m trän trong C , nh­ng nÕu xuÊt ph¸t tõ x = 0 th× ®iÒu nµy kh«ng ®óng. Cho C ⊆ Rn lµ tËp låi vµ x ∈ C . Ký hiÖu NC (x) = {w | hw, y − xi ≤ 0, ∀y ∈ C} . HiÓn nhiªn 0 ∈ NC (x). Dïng ®Þnh nghÜa dÔ kiÓm tra ®­îc r»ng NC (x) lµ nãn låi ®ãng. Nãn nµy ®­îc gäi lµ nãn ph¸p tuyÕn ngoµi cña gäi lµ nãn ph¸p tuyÕn trong cña C t¹i x. TËp −NC (x) ®­îc C t¹i x. −NC (x) = {w | hw, y − xi ≥ 0 ∀y ∈ C} . 12 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mét nãn quan träng kh¸c lµ nãn ®èi cùc ®­îc ®Þnh nghÜa nh­ sau: C ∗ = {w | hw, xi ≥ 0 ∀x ∈ C} . §©y còng lµ mét nãn låi ®ãng chøa gèc. Cho C lµ tËp låi, kh¸c rçng vµ x ∈ C . Ta nãi d ∈ Rn lµ mét h­íng chÊp nhËn ®­îc cña C nÕu ∃t0 > 0 sao cho x + td ∈ C víi mäi 0 ≤ t ≤ t0 . TËp tÊt c¶ c¸c h­íng chÊp nhËn ®­îc lµ mét nãn låi chøa gèc vµ gäi lµ nãn chÊp nhËn ®­îc. Ký hiÖu lµ FC (x). Nãn nµy cã thÓ kh«ng ®ãng, tuy nhiªn nÕu lÊy bao ®ãng, ta sÏ ®­îc mét nãn kh¸c gäi lµ nãn tiÕp xóc cña Ký hiÖu nãn nµy lµ C t¹i x. TC (x), th× FC (x) = TC (x). Tõ ®©y suy ra  TC (x) = d ∈ Rn | ∃dk → d, ∃tk & 0 : x + tk dk ∈ C ∀k . MÖnh ®Ò 1.1.24. ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.8). Nãn ph¸p tuyÕn vµ nãn tiÕp xóc lµ ®èi cùc cña nhau. DÔ dµng suy trùc tiÕp tõ ®Þnh nghÜa. VÝ dô 1.1.25. Gi¶ sö tËp låi C ®­îc cho bëi  C = x ∈ Rn | haj , xi ≤ bj , j = 1, . . . , m víi x ∈ C , ®Æt  J(x) = j | haj , xi = bj gäi lµ tËp chØ sè tÝch cùc t¹i x. Khi ®ã  TC (x) = x ∈ Rn | haj , xi ≤ 0, j ∈ J(x) . P NC (x) = cone (aj , j ∈ J(x)) = {y = λj aj : λj ≥ 0}. j∈J(x) 1.2 Hµm låi. Trong ch­¬ng tr×nh to¸n phæ th«ng, chóng ta ®· lµm quen víi kh¸i niÖm hµm låi mét c¸ch c¬ b¶n. Môc nµy, chóng t«i tr×nh bµy kh¸i niÖm tæng qu¸t vÒ hµm låi vµ mét sè tÝnh chÊt cña nã. 13 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Cho tËp §Þnh nghÜa 1.2.1. C ⊂ Rn vµ f : C → R Ta sÏ ký hiÖu : dom f = {x ∈ C | f (x) < +∞} , epi f = {(x, µ) ∈ C × R | f (x) ≤ µ} . C¸c tËp dom f , epi f lÇn l­ît ®­îc gäi lµ miÒn h÷u hiÖu vµ trªn ®å thÞ cña hµm f. B»ng c¸ch cho f (x) = +∞ nÕu x 6∈ C , ta cã thÓ coi f ®­îc x¸c ®Þnh trªn toµn kh«ng gian vµ dom f = {x ∈ Rn | f (x) < +∞} , epi f = {(x, µ) ∈ Rn × R | f (x) ≤ µ} . Quy ­íc nÕu λ = 0 th× λf (x) = 0 víi mäi x. §Þnh nghÜa 1.2.2. trªn Cho ∅= 6 C ⊆ Rn låi vµ f : C → R. Ta nãi f lµ hµm låi C nÕu epif lµ mét tËp låi trong Rn+1 . Hµm f ®­îc gäi lµ hµm lâm trªn C nÕu −f lµ hµm låi trªn C. Sau ®©y chñ yÕu ta xÐt hµm f : Rn → R ∪ {+∞}. DÔ thÊy ®Þnh nghÜa trªn t­¬ng ®­¬ng víi: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) trong ®ã ∀x, y ∈ C , ∀λ ∈ (0, 1). §Þnh nghÜa 1.2.3. Hµm f : Rn → R ∪ {+∞} ®­îc gäi lµ låi chÆt trªn C nÕu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1). Hµm f : Rn → R ∪ {+∞} ®­îc gäi lµ låi m¹nh trªn C víi hÖ sè η > 0 nÕu 1 f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − ηλ(1 − λ) k x − y k2 2 ∀x, y ∈ C, ∀λ ∈ (0, 1). 14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn NhËn xÐt 1.2.4. DÔ dµng kiÓm tra r»ng, f låi m¹nh trªn khi vµ chØ khi hµm h(.) = f (.) − låi trªn C víi hÖ sè η > 0 1 k . k2 2 C. Sau ®©y, ta sÏ ®Ò cËp ®Õn mét bÊt ®¼ng thøc quen thuéc trong ch­¬ng tr×nh phæ th«ng. §©y lµ bÊt ®¼ng thøc t­¬ng ®èi tæng qu¸t trong c¸c bÊt ®¼ng thøc vÒ hµm låi. C¸c bÊt ®¼ng thøc Cauchy, Bunhia...lµ nh÷ng tr­êng hîp riªng cña bÊt ®¼ng thøc nµy. BÊt ®¼ng thøc Jensen: NÕu f lµ hµm låi vµ nhËn gi¸ trÞ h÷u h¹n trªn tËp låi ∀x1 , . . . , xm ∈ C vµ ∀λj ≥ 0 tháa m·n m P C th× ∀m ∈ N∗ , λj = 1, ta cã: j=1 m m X X j f( λj x ) ≤ λj f (xj ). j=1 MÖnh ®Ò 1.2.5. j=1 ( xem [2], Ch­¬ng 8, MÖnh ®Ò 8.1). Mét hµm lµ låi trªn C khi chØ khi f :C →R ∀x, y ∈ C , ∀α > f (x), ∀β > f (y), ∀λ ∈ [ 0, 1] , ta cã f (λx + (1 − λ)y ≤ λα + (1 − λ)β. Chøng minh. §iÒu kiÖn cÇn: Chän Gi¶ sö f låi. chän x, y, α, β nh­ ®· nªu trong mÖnh ®Ò. α0 ∈ (f (x), α) vµ β 0 ∈ (f (y), β). VËy (x, α0 ), (y, β 0 ) ∈ epi f . Do epi f låi nªn ((1 − λ)x + λy, (1 − λ)α0 + λβ 0 ) ∈ epi f. ⇒ f ((1 − λ)x + λy) ≤ (1 − λ)α0 + λβ 0 < (1 − λ)α + λβ. §iÒu kiÖn ®ñ: Chän (x, µ), (y, η) ∈ epi f vµ λ ∈ (0, 1). Víi mäi  > 0, ta cã: f (x) < µ + , f (y) < η + . 15 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Do ®ã: f [ (1 − λ)α0 + λβ 0 ] < (1 − λ)(µ + ) + λ(η + ) = (1 − λ)µ + λη + . ⇒ (1 − λ)(x, µ) + λ(y, η) ∈ epi f. VËy f låi. D­íi ®©y lµ mét ®Þnh nghÜa kh¸c, t­¬ng ®­¬ng vÒ hµm låi, låi m¹nh dùa vµo kh¸i niÖm hÖ sè låi. Hµm §Þnh nghÜa 1.2.6. f : Rn → R ∪ {+∞} ( kh«ng nhÊt thiÕt låi ). C ⊆ Rn lµ mét tËp låi kh¸c rçng vµ η lµ mét sè thùc. Ta nãi η lµ hÖ sè låi cña f trªn C , nÕu víi ∀λ ∈ (0, 1), ∀x, y ∈ C , ta cã: 1 f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − ηλ(1 − λ) k x − y k2 . 2 HiÓn nhiªn nÕu η = 0 th× f låi trªn C . NÕu f cã hÖ sè låi trªn C lµ η > 0 th× f låi m¹nh trªn C víi hÖ sè η. §Þnh nghÜa 1.2.7. Mét hµm f ®­îc gäi lµ chÝnh th­êng nÕu dom f 6= ∅ vµ f (x) > −∞ víi mäi x. Hµm f ®­îc gäi lµ ®ãng nÕu epi f lµ mét tËp ®ãng trong Rn+1 . Chó ý 1.2.8. a) Tõ ®Þnh nghÜa cña ®Þnh nÕu biÕt b) NÕu epi f , ta thÊy r»ng mét hµm låi hoµn toµn ®­îc x¸c epi f. f lµ mét hµm låi trªn mét tËp låi C th× cã thÓ th¸c triÓn f lªn toµn kh«ng gian b»ng c¸ch ®Æt fe (x) = HiÓn nhiªn fe (x) +∞ nÕu x 6∈ C. = f (x) víi ∀x ∈ C vµ fe låi trªn Rn . H¬n n÷a fe lµ chÝnh th­êng khi chØ khi c) NÕu ( f (x) nÕu x ∈ C f chÝnh th­êng. T­¬ng tù fe ®ãng khi vµ chØ khi f ®ãng. f låi trªn Rn suy ra domf låi. V× domf lµ h×nh chiÕu trªn C cña epif . dom f = {x : f (x) < +∞} = {x : ∃µ, (x, µ) ∈ epif } . 16 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn VËy domf lµ ¶nh cña tËp låi epif qua mét ¸nh x¹ tuyÕn tÝnh. Do ®ã, domf låi. VÝ dô 1.2.9. Mét sè hµm låi 1. Hµm a-phin: f (x) = ha, xi + α, trong ®ã a ∈ Rn , α ∈ R. DÔ dµng kiÓm tra ®­îc r»ng Khi f lµ hµm võa låi võa lâm trªn toµn kh«ng gian. α = 0, th× hµm nµy ®­îc gäi lµ hµm tuyÕn tÝnh. Cho C 6= ∅ lµ mét tËp låi. 2. Hµm chØ: §Æt ( 0 nÕu x ∈ C, δC (x) = +∞ nÕu x 6∈ C. Ta nãi δC lµ hµm chØ cña C . Do C låi nªn δC lµ mét hµm låi. 3. Hµm mÆt cÇu: Cho S = {x ∈ Rn | k x k= 1} lµ mét mÆt cÇu vµ h : S → R+ lµ mét hµm bÊt kú.  nÕu k x k< 1,  0 f (x) = h(x) nÕu k x k= 1,   +∞ nÕu k x k> 1. hµm nµy ®ùoc gäi lµ hµm mÆt cÇu. DÔ thÊy r»ng mÆc dï f lµ mét hµm låi trªn Rn , h lµ mét hµm kh«ng ©m bÊt kú trªn mÆt cÇu S . 4. Hµm tùa: Hµm d­íi ®©y ®­îc gäi lµ hµm tùa cña C SC (y) = sup< y, x >. x∈C 5. Hµm kho¶ng c¸ch: Cho C låi ®ãng, hµm kho¶ng c¸ch ®Õn tËp C ®­îc ®Þnh nghÜa bëi dC (x) = mink x − y k. y∈C 6. Hµm chuÈn: Gi¶ sö x = (x1 , . . . , xn ). f (x) =k x k= max| xi | i hoÆc 1 f (x) =k x k= (x1 2 + . . . + xn 2 ) 2 . 17 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ch­¬ng 2 PhÐp chiÕu lªn tËp låi ®ãng. Bµi to¸n t×m h×nh chiÕu vu«ng gãc cña mét ®iÓm xuèng tËp låi cã vai trß quan träng trong tèi ­u vµ nhiÒu lÜnh vùc kh¸c nh­ bÊt ®¼ng thøc biÕn ph©n, c©n b»ng...Bµi to¸n nµy cã rÊt nhiÒu øng dông, ®Æc biÖt nã xuÊt hiÖn nh­ mét bµi to¸n phô trong rÊt nhiÒu ph­¬ng ph¸p sè tèi ­u, bÊt ®¼ng thøc biÕn ph©n. §©y còng lµ c«ng cô s¾c bÐn vµ kh¸ ®¬n gi¶n ®Ó chøng minh nhiÒu ®Þnh lý quan träng nh­ ®Þnh lý t¸ch,...mµ ta sÏ xÐt ë ch­¬ng sau. Nh÷ng c¸ch chøng minh dùa trªn phÐp chiÕu vu«ng gãc th­êng mang tÝnh chÊt kiÕn thiÕt. 2.1 §Þnh nghÜa vµ tÝnh chÊt. §Þnh nghÜa 2.1.1. Cho C 6= ∅ (kh«ng nhÊt thiÕt låi) vµ y lµ mét vÐc-t¬ bÊt kú, ®Æt dC (y) = inf k x − y k . x∈C Ta nãi dC (y) lµ kho¶ng c¸ch tõ NÕu tån t¹i vu«ng gãc y ®Õn C . π ∈ C sao cho dC (y) =k π − y k th× ta nãi π lµ cña y trªn C . Ta ký hiÖu h×nh chiÕu cña y trªn C lµ pC (y). Th«ng th­êng sÏ ký hiÖu π cÇn nhÊn m¹nh ®Õn tËp chiÕu Chó ý r»ng, nÕu h×nh chiÕu = pC (y) hoÆc ®¬n gi¶n h¬n lµ p(y) nÕu kh«ng C. y ∈ C th× dC (y) = 0. NÕu C 6= ∅ th× dC (y) h÷u h¹n v× 0 ≤ dC (y) ≤k y − x k víi mäi x ∈ C. Theo ®Þnh nghÜa, ta thÊy r»ng h×nh chiÕu pC (y) cña y trªn C sÏ lµ nghiÖm 18 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- Xem thêm -