Tài liệu Chặn sai số cho hệ đa thức trong không gian hữu hạn chiều (

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 TRẦN ĐÌNH THẮNG CHẶN SAI SỐ CHO HỆ ĐA THỨC TRONG KHÔNG GIAN HỮU HẠN CHIỀU LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 TRẦN ĐÌNH THẮNG CHẶN SAI SỐ CHO HỆ ĐA THỨC TRONG KHÔNG GIAN HỮU HẠN CHIỀU Chuyên ngành: Toán Giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. HOÀNG NGỌC TUẤN HÀ NỘI, 2017 i Lời cảm ơn Luận văn được thực hiện và hoàn thành tại Trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn khoa học của TS. Hoàng Ngọc Tuấn. Qua đây, tác giả xin được gửi lời cảm ơn sâu sắc đến thầy giáo, người hướng dẫn khoa học của mình, TS. Hoàng Ngọc Tuấn, người đã đưa ra đề tài và tận tình hướng dẫn trong suốt quá trình nghiên cứu của tác giả. Đồng thời tác giả cũng chân thành cảm ơn tới toàn thể quý thầy cô trong Trường Đại học Sư phạm Hà Nội 2 đã tận tình truyền đạt kiến thức cũng như tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình học tập nghiên cứu và cho đến khi hoàn thành luận văn. Xin chân thành bày tỏ lòng biết ơn đến toàn thể quý thầy cô trong trường THPT Quế Võ số 1 – Bắc Ninh đã động viên giúp đỡ tác giả trong quá trình học tập và làm luận văn. Mặc dù đã có nhiều cố gắng, song kiến thức và kinh nghiệm bản thân còn nhiều hạn chế nên luận văn không thể tránh khỏi những thiếu sót, tác giả mong được sự đóng góp ý kiến của các thầy cô giáo, các bạn học viên. Em xin chân thành cảm ơn! Hà Nội, tháng 12 năm 2017 Học viên Trần Đình Thắng ii Lời cam đoan Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Học viên Trần Đình Thắng iii Mục lục Trang Lời cảm ơn i Lời cam đoan ii Mục lục iii Mở đầu iv Chương 1. Chặn sai số cho hệ đa thức tổng quát 1 1.1. Khái niệm chặn sai số 1 1.2. Chặn sai số cho đa thức tổng quát 2 1.2.1. Chặn sai số cho hệ đa thức 2 1.2.2. Chặn sai số cho hệ bất đẳng thức lồi bậc hai 5 Chương 2. Chặn sai số cho đa thức lồi 13 2.1. Một số tính chất của đa thức lồi 13 2.1.1. Định nghĩa và một số kết quả 13 2.1.2. Một số tính chất của đa thức lồi 17 2.2. Chặn sai số cho đa thức lồi 21 2.2.1. Chặn sai số cho đa thức lồi 21 2.2.2. Chặn sai số cho đa thức lồi trong miền đa diện 31 Kết luận 36 Tài liệu tham khảo 37 iv Mở đầu 1. Lý do chọn đề tài: Chặn sai số cho một tập hợp trong không gian Euclid là một bất đẳng thức giới hạn khoảng cách từ các véctơ trong một tập thử nghiệm đến một tập cho trước thông qua hàm thặng dư. Gần đây, lý thuyết về chặn sai số đã có những ứng dụng quan trọng trong nhiều lĩnh vực khác nhau của quy hoạch toán học, như phân tích độ nhạy, phân tích sự hội tụ của thuật toán và giải tích tiệm cận. Với mong muốn tìm hiểu kỹ hơn về lý thuyết chặn sai số, dưới sự hướng dẫn của TS. Hoàng Ngọc Tuấn tôi đã chọn đề tài “Chặn sai số cho hệ đa thức trong không gian hữu hạn chiều” để thực hiện luận văn của mình. 2. Mục đích nghiên cứu: - Luận văn nghiên cứu về chặn sai số cho hệ đa thức tổng quát - Luận văn nghiên cứu về chặn sai số cho đa thức lồi. 3. Nhiệm vụ nghiên cứu: - Nghiên cứu về chặn sai số cho đa thức tổng quát và đa thức lồi 4. Đối tượng và phạm vi nghiên cứu: - Đối tượng nghiên cứu: Chặn sai số cho đa thức. - Phạm vi nghiên cứu: Nghiên cứu chặn sai số cho đa thức tổng quát và đa thức lồi. 5. Những đóng góp mới của đề tài: - Trình bày một cách có hệ thống về chặn sai số cho hệ đa thức tổng quát và chặn sai số cho đa thức lồi. v 6. Phương pháp nghiên cứu: - Vận dụng các kiến thức, phương pháp của giải tích hàm, giải tích không trơn, lý thuyết tối ưu - Phân tích và tổng hợp, hệ thống các kiến thức, phương pháp liên quan đến chặn sai số cho đa thức. 1 Chương 1 Chặn sai số cho hệ đa thức tổng quát Trong chương này chúng ta nêu khái niệm cơ bản về chặn sai số, và trình bày các tính chất chặn sai số cho đa thức tổng quát và chặn sai số cho hệ bất đẳng thức lồi bậc hai. Những kiến thức trình bày ở đây lấy chủ yếu từ trong bài báo [5]. 1.1. Khái niệm Chặn sai số Cho hàm số  : S :  x  n n  , tập mức dưới của  được định nghĩa là :  ( x)  0. Chúng ta nói rằng  có chặn sai số với bậc  nếu có   0 sao cho d ( x, S )    ( x)  x   n , trong đó  ( x)  max  ( x),0 và d  x, S  kí hiệu khoảng cách từ x tới S . Nếu  có chặn sai số bậc 1, ta cũng nói  có chặn sai số tuyến tính. Tập nghiệm tối ưu của  được gọi là argmin  ( x). Xét hệ bất đẳng thức: f1 ( x)  0, f 2 ( x)  0,..., f m ( x)  0, g1( x)  0, g2( x)  0,..., g k ( x)  0, trong đó x n (1.1) và fi , g j là hàm khả vi của x . Kí hiệu P là tập nghiệm của (1.1), giả sử P  . Cho f : n  m là hàm véc tơ, hàm thành phần thứ i của f kí hiệu là fi . Cho g được xác định tương tự. Trong trường hợp đặc biệt khi f , g là ánh xạ tuyến tính afin, nghĩa là f ( x)  Ax  a, g ( x)  Bx  b với A, B là ma trận và a, b là véc tơ có số chiều phù hợp. Hoffman [4] chỉ ra một kết quả cơ bản: tồn tại   0 phụ thuộc vào A và B sao cho dist ( x, P)     Ax  a    Bx  b x  n , (1.2) 2 ở đó dist .,. là hàm khoảng cách Euclide giữa hai tập, . là chuẩn Euclide thông thường trong n và . là phần dương của một vec tơ. Nói cách khác, khoảng cách từ véc tơ x bất kỳ thuộc n đến P có thể bị chặn trên bởi số vi phạm của các ràng buộc tại x. Công thức (1.2) đánh giá tính liên tục Lipchitz của tập nghiệm của hệ tuyến tính khi vế phải bị thay đổi. Ví dụ 1.1. Cho f :  xác định f ( x)  x 2 . Hiển nhiên tập nghiệm P  x | f (x)  0 chứa một điểm cô lập là gốc. Cho x bất kỳ thuộc với x  0, ta có dist ( x, P)  x . Tuy nhiên, lượng vi phạm của ràng buộc x 2  0 là  f ( x)  x 2 . Vậy, chặn sai số (1.2) không đúng với x gần gốc ( x  0). Thay vào đó, ta có dist ( x, P)   f ( x) 1 2 . Ví dụ 1.1 chỉ ra rằng kết quả của Hoffman (1.2) không đúng với ánh xạ đa thức nói chung. Nghĩa là, tính liên tục Lipschitz của tập nghiệm bị mất khi ta xét hàm không tuyến tính. Điều này gợi ý ta thay thế (1.2) bởi công thức tổng quát sau: dist ( x, P)   với mọi x  n   f ( x)    g ( x) ,  (1.3) , trong đó  ,  là hằng số dương chỉ phụ thuộc vào hệ số và bậc của đa thức f1,..., f m , g1,..., gk . Nói cách khác tập nghiệm của hệ đa thức phi tuyến là Holder liên tục phải. Thật vậy, Hormander là người đầu tiên thiết lập (1.3) với trường hợp f ( x) là đơn thức, mặc dù thêm một thừa số 1  x cần thiết trong vế phải (  '  0 là hằng số). 1.2. Chặn sai số cho đa thức tổng quát 1.2.1. Chặn sai số cho hệ đa thức  ' là 3 Trong phần này, ta chỉ ra rằng chặn sai số (1.3) là đúng, nếu không kể tới thừa số 1  x  ' ( '  0 là hằng số) đã được giới thiệu. Kết quả sau dựa vào kết quả chặn sai số của Hormander, với f là đơn thức. Định lý 1.2.1 Cho f ( x) là một đa thức thực với các biến x1,..., xn . Kí hiệu P là tập các nghiệm thực của f , nghĩa là, P  x | f ( x)  0, x  ( x1,..., xn , và giả sử P khác rỗng. Khi đó tồn tại các hằng số dương  ,  và hằng số  ' (có thể âm) sao cho dist ( x, P)   1  x  ' f ( x)  x  . (1.4) Sau đây ta sẽ mở rộng Định lý 1.2.1 với hệ phương trình của đa thức và bất đẳng thức. Ý tưởng là ta thêm một biến yếu vào (1.1), chuyển đổi thành hệ tương đương với một phương trình đơn thức, sau đó áp dụng Định lý 1.2.1 với hệ số mới này. Định lý 1.2.2. Cho P là tập các x thỏa mãn f1 ( x)  0,..., f m ( x)  0, g1 ( x) n  0,..., gk ( x)  0, ở đó f i và g j là đa thức với hệ số thực. Giả sử P khác rỗng. Khi đó tồn tại hằng số   0,   0, và  '  0 sao cho dist ( x, P)   1  x    f ( x)  '   g ( x)  , x   n . (1.5) Ở đây f ( x)  ( f1 ( x),..., f m ( x))T và g ( x)  ( g1 ( x),..., gk ( x))T . Chứng minh. Xét đa thức h : n m được cho bởi h( x, z )   f1 ( x)  z12   ...   f m ( x)  zm2   g12 ( x)  ...  g k2 ( x), 2 trong đó z  ( z1,....zm )T . Cho P  2 n m (1.6) là tập các ( x, z ) sao cho h( x, z )  0. Dễ thấy rằng x  P  ( x, z )  P với zi   fi ( x) , i  1,..., m. (1.7) 4 Vì P khác rỗng, cho nên P khác rỗng. Theo Định lý 1.2.1, tồn tại các hằng số   0,   0, và  '  0 sao cho dist (( x, z ), P )   1  ( x, z )  dương). Cho x  với zi  n , z m ' h( x, z )  với mọi ( x, z )   fi ( x) , n m . (Giả sử  ' i  1,..., m. Cho ( x* , z* )  P sao cho ( x, z )  ( x* , z* )  dist  ( x, z ), P . Khi đó ta có x  x*  ( x, z )  ( x * , z * )     1  ( x, z )  = dist ( x, z ), P   1  x  z ' h ( x, z )    f ( x )  ' 2  1  ...   f m ( x)  g ( x)  ...  g ( x)   1  x    f ( x) 2   1  x    f ( x)  g ( x) '  ' 2  g ( x) 2  2 1 2 k   (1.8)  (1.9) ,  trong đó (1.8) được suy ra từ (1.6) và fi ( x)  zi2  fi ( x)    fi ( x)   fi ( x) , i  1,..., m, và (1.9) được suy ra từ zi2  fi ( x)  c 1  x  L , trong đó i  1,..., m với mọi hằng số c, L dương. Cho  ,  ' đủ lớn, đặt   2 ta suy ra điều phải chứng minh. Chặn sai số được cho bởi Định lí 1.2.2 yếu hơn chặn sai số Hoffman (1.2). Đầu tiên, nó có thêm thừa số 1  x  ' . Ta có thể khử thừa số này bằng cách hạn chế chặn sai số trên một miền bị chặn. Hệ quả 1.2.3. Cho f1,..., f m , g1,...gk , và P như trong Định lý 1.2.2. Cho  là số dương sao cho x   , x  P. Khi đó ta có 5 dist ( x, P)   '   f ( x)  g ( x)   x với x   , với mỗi  '  0 và   0. Chứng minh. Áp dụng Định lý 1.2.2, và cho  '   (1   ) ' , (  0). Ví dụ sau chỉ ra rằng thừa số 1  x  ' không thể bỏ được trong chặn sai số (1.5). Ví dụ 2.1. Xét hệ bậc hai trong 2 : x1x2  0, x1  0, x2  1. Rõ ràng, tập nghiệm của hệ là P  (0, x2 ) | x2  1. Xét điểm (t ,0) trên trục x1 với t  0. Thế thì phần dư đánh giá tại (t ,0) bằng 1. Tuy nhiên khoảng cách từ (t ,0) đến P ít nhất bằng t, nghĩa là nó không bị chặn khi t  . Vậy chặn sai số (1.5) không đúng với x  n nếu thừa số 1  x  ' bị khử. 1.2.2. Chặn sai số cho hệ bất đẳng thức lồi bậc hai Xét hệ bất đẳng thức lồi bậc hai được cho bởi f1 ( x)  0,..., f m ( x)  0 , (1.10) trong đó fi ( x)  x,Qi ( x) / 2  bi , x  ci , i  1,2,..., m, với mỗi Qi là ma trận i xác định dương cấp n  n, b là n véc tơ, và ci là một số thực. Kí hiệu N là tập chỉ số i sao cho f i phi tuyến và L là tập chỉ số i sao cho f i tuyến tính. P là tập nghiệm của (1.10). Ta đưa ra giả thiết sau về hệ bất đẳng thức bậc hai (1.10). * Giả thiết 1.10: Tồn tại x  P sao cho fi ( x* )  0 với mọi i  N . Nói cách * khác, x thỏa mãn điều kiện phi tuyến của (1.10) với bất đẳng thức chặt. Dưới Giả thiết (1.10) ta sẽ chứng minh rằng chặn sai số của Hoffman đúng với hệ bất đẳng thức bậc hai lồi (1.10). Đặc biệt, ta có kết quả sau. 6 Định lý 1.2.4. Giả sử rằng Giả thiết 1.10 đúng. Khi đó tồn tại số dương  phụ thuộc vào dữ kiện bài toán sao cho dist ( x, P)    f ( x) x  n (1.11) , trong đó f ( x)   f1 ( x), f 2 ( x),..., f m ( x)  . T Như đã lưu ý, chặn sai số (1.11) được xây dựng bởi Mangasarian cho hệ bất đẳng thức lồi khả vi, dưới giả thiết tương tự Giả thiết 1.10 cộng thêm ràng buộc tiệm cận. Định lý 1.2.5 (Mangasarian, [7]). Cho f là hàm lồi khả vi từ n  m . Cho N  L là một phân hoạch của 1,...,m sao cho f N phi tuyến và f L tuyến tính, và cho P   x | f ( x)  0. Giả sử tồn tại x*  P sao cho f N ( x* )  0 và hằng số  xác định bởi   n sup , x,I  I x  P, I  0, f I ( x)  0,  iI ifi ( x)  1, fi ( x) độc lập tuyến tính, I  {1,..., m} (1.12) là hữu hạn. Thế thì dist ( x, S )    f ( x) x  n . (1.13) Hơn nữa, khi một điều kiện ràng buộc tiệm cận thỏa mãn, hằng số  định nghĩa bởi (1.12) là hữu hạn. Nhưng điều kiện (1.12) và điều kiện ràng buộc tiệm cận không dễ để xác định (xem [7]). Ta sẽ chỉ ra rằng đối với hệ bất đẳng thức bậc hai lồi (1.10), hằng số  luôn hữu hạn và điều kiện ràng buộc tiện cận Mangasarian có thể được lược bỏ. Bổ đề 1.2.6. Với Q là ma trận đối xứng xác định dương cấp n  n, tồn tại hai hằng số u và v sao cho u Qx  x, Qx  v Qx , 2 2 7 với mọi x n . Bổ đề 1.2.7. Giả sử Q1 ,..., Q k là các ma trận đối xứng xác định dương cấp n  n. Cho  là hằng số dương. Khi đó, với mọi 1,..., k với i  0, i  1,..., k , ta có  2 2 1Q1x  ...  k Qk x   Q1x  ...  Q k x 2  x  n , ở đó  là hằng số dương chỉ phụ thuộc vào  và Q1 , Q2 ,..., Qk . n Chứng minh. Cố định x  . Lấy y  n sao cho  y  M Q1 y  ...  Qk y , Q1 y  Q1x,..., Q k y  Q k x, (1.14) ở đó M là hằng số chỉ phụ thuộc vào Q1 ,...., Q k (Sự tồn tại của y và M được đảm bảo bởi chặn sai số Hoffman (1.2) ). Theo Bổ đề 1.2.6, tồn tại u  0 chỉ 2 phụ thuộc vào Q1 ,...., Q k sao cho Qi y  y, Qi y / u, với mọi i. Vậy, ta có 2 Qi y  y, Qi y / u  1 y,(1Q1  ...  k Q k ) y u  M Q1 y  ...  Q k y u   ( Q  ...   Q ) y 1 k 1 k i, ở đó bước chứng minh thứ hai được suy ra từ i   và Qi  0 ( Q i xác định dương) i  1,...k , và bước chứng minh cuối được suy ra từ bất đẳng thức Cauchy- Schwarz và (1.14) . Lấy tổng các bất đẳng thức trên với mọi i và sử dụng bất đẳng thức Cauchy- Schwarz một lần nữa ta được k Qy i i 1 2   Mk Q1 y  ...  Q k y u Mk  u 3 2 Qy 1 2  ( Q  ...   Q ) y 1 1  ...  Q y k  1 2 2 k k (1Q1  ...  k Q k ) y . 8 Khử đi hệ số Qy 1 2  ...  Q y k  1 2 2 và sử dụng Qi y  Qi x, i ta được điều phải chứng minh. Bổ đề dưới đây là cần thiết để chứng minh Định lý 1.2.4. Bổ đề 1.2.8. Giả sử Giả thiết 1.10 đúng. Khi đó tồn tại hằng số   0 (chỉ phụ thuộc vào dữ kiện bài toán) sao cho   (Q x  b )    b i i i iN iL i i      i   iN  b iL i i  ,  (1.15) với mọi   0 và với mọi x mà fi ( x)  0, i  1,..., m, trong đó N là tập chỉ số phi tuyến, L là tập chỉ số tuyến tính. Chứng minh. Ta có thể giả sử x*  0, trong trường hợp này Giả thiết 1.10 suy ra ci  0 với i  N và ci  0 với i  L. Ta sẽ chứng minh (1.15) bằng quy nạp theo N , lực lượng của tập N . Rõ ràng (1.15) đúng khi N  0. Giả sử khẳng định là đúng với N  k ; ta chứng minh khẳng định đúng với N  k  1. Giả sử ngược lại, tồn tại dãy  x r  và  r  sao cho   (Q x iN r i i r  bi )   ir bi  0, (1.16) iL trong đó  iN Vì  b iL r i r i i   b iL r i i  1, ir  0, fi ( x r )  0, i  1,..., k  1. (1.17) bị chặn, bởi chặn sai số của Hoffman, không mất tính tổng quát, giả sử ir  , i  L, bị chặn. Chú ý ir  , i  N , cũng bị chặn. Do đó bằng cách bỏ qua một dãy con nếu cần, ta giả sử rằng, với mỗi i  N  L, dãy ir  hội tụ đến giới hạn i  0. Cho N1  N là tập các chỉ số i sao cho i  0, và 9 N1 là phần bù của N1 trong N. Ta khẳng định rằng N1  N . Giả sử ngược lại, ir   , với mọi r , với mọi i  N và   0 . Từ (1.16) - (1.17),   Q x , i  N , bị chặn. Vì bị chặn. Do đó từ Bổ đề 1.2.7 suy ra i r iN ir Qi x r  fi ( x r )  0, suy ra bi x r  cũng bị chặn, với mọi i. Vậy bằng cách lược bỏ phần của x r mà Qi x r  0 và bi x r  0, ta có thể giả sử  x r  bị chặn. Cho x  là điểm tụ của x . Khi đó r fi ( x )  0 với mọi i  iN  i (Qi x  bi )   ibi  0. iL Cho f ( x)   iN L i fi ( x). Thế thì f ( x )  0 và f ( x )  0. Vì i không âm, f ( x) lồi. Do đó, f ( x) đạt được cực tiểu toàn cục (trong n  ), là 0, tại x . Tuy nhiên, vì i  0 với mọi i  N , nên Giả thiết 1.10 suy ra f ( x* )  0, mâu thuẫn. Vậy, N1 phải là tập con thực sự của N. Ta khẳng định rằng ir Qi x r   , r  r0 , i  N1, (1.18) với hằng số dương  và chỉ số r0 nào đó. Nếu (1.18) không đúng, thì tồn tại chỉ số j  N1 và dãy con R sao cho  Q x  r j j r rR hội tụ đến 0. Do đó (1.16) và    0 dẫn tới r j  iN ,i  j ir (Q r x r  br )   ir bi  0, r  R, iL và  iN ,i  j ir   b iL r i i  1. 10 Hai mối quan hệ trên cùng với fi ( xr )  0, ir  0 suy ra (1.15) không đúng với N \  j mà có lực lượng là k . Mâu thuẫn với giả thiết quy nạp. Vậy (1.18) đúng. Với mỗi r  r0 , xét hệ tuyến tính theo y Qyi  Qi x r , bi , y  b j , x r , i  N , j  N1  L. (1.19) Rõ ràng, x r là nghiệm của hệ tuyến tính trên. Vậy bởi chặn sai số của Hoffman (1.2), (1.19) có nghiệm y r với tính chất   y r  M   Q i y r   bi , y r  , iN1  L  iN  (1.20) trong đó M là hằng số dương phụ thuộc vào r. Theo Bổ đề 1.2.6, tồn tại u  0 (chỉ phụ thuộc vào Q i ) sao cho Qi y r , y r  u Qi y r 2 r. Vậy, ta có 2 2 ir Qi y r , y r  uir Qi y r  uir Qi x r  u Qi x r  u Qi y r , i  N1 , r  r0 , trong đó các đẳng thức được suy ra từ Qi x r  Qi y r và bất đẳng thức thứ hai là do (1.18) . Vì y r thỏa mãn (1.19), nên fi ( y r )  fi ( x r )  0, với mọi i  N1  L. Vậy, ta có bi , y r  ci  y r , Qi y r / 2, i  N1. bi , y r  ci , i  L và Đưa ba quan hệ trên áp dụng vào (1.20) ta được  ir Qi y r , y r y  M   iN   iN 1 1  u  Qi y r , y r r + iN L ci   iN 1 1 u y ,Q y  .  2  r i r (1.21) 11 Tương tự, từ fi ( y r )  0 ta có Qi y r  bi , y r  ci  y r , Qi y r / 2  0, i  N1 , (1.22) trong đó ci  0, i  N1 và Q i xác định dương. Sử dụng (1.21) - (1.22) và (1.16) ta rút ra mâu thuẫn. Đặc biệt từ (1.16) và ir   0 với i  N1 , ta có   r i r i r i r r i   i (Q y  b )   i Q y   i b   0. iL iN1  iN1  Chú ý bi , y r  bi , x r  ci , i  L (theo (1.19)). Vì vậy, nhân vô hướng của biểu thức trên với y r / y r ta có Qi y r , y r  iN1 r i   yr iN1 r i Q i y r  bi , y r yr ci  0. yr   ir iL Vì Q i nửa xác định dương, nên mọi số hạng của tổng đầu tiên không âm, và theo (1.22) và ci  0, nên số hạng trong hai tổng sau không âm. Vậy ta có  r i iN1 Qi y r , y r y r   0, iN1 ci y r  0,  iN1 Qi y r , y r y r  0,  r i iL ci yr  0. (1.23) Xét hai trường hợp. Trường hợp 1: N1  . Khi đó N1  N , mối quan hệ đầu tiên của (1.23) và (1.21) suy ra y  r bị chặn. Vì Qi x r  Qi y r và ir  0 với i  N1 , nên ir Qi x r  0, mâu thuẫn (1.18). Trường hợp 2: N1  . Mối liên hệ thứ hai của (1.23) suy ra y r  , bởi vì ci  0 với i  N1. Điều này, cùng mối liên hệ thứ ba của (1.23), suy ra  iN1 Qi y r , y r yr  0. (1.24) 12 Ta thấy (1.23) - (1.24) mâu thuẫn với (1.21), suy ra điều phải chứng minh. Rõ ràng, Bổ đề 1.2.8 suy ra điều kiện (1.12). Vậy chặn sai số (1.13) đúng với hệ bậc hai lồi thỏa mãn Giả thiết 1.10. Điều này chứng minh định lý 1.2.4. So sánh với chặn sai số Hoffman (1.2) cho hệ tuyến tính, thì chặn sai số (1.11) có điểm yếu; cụ thể, nó chỉ áp dụng cho hệ bất đẳng thức bậc hai lồi. Nhìn chung, chặn sai số không đúng nếu có ràng buộc đẳng thức vì có thể mất tính lồi. Tuy nhiên, nếu ràng buộc đẳng thức là tuyến tính thì chặn sai số (1.11) vẫn đúng. Đặc biệt, xét hệ bậc hai lồi Ax  a, f1 ( x)  0, f 2 ( x)  0,...., f m ( x)  0. Cho P là tập nghiệm. Sử dụng Định lý 1.2.4, ta có thể chứng minh điều sau. Hệ quả 1.2.9. Giả sử tồn tại x*  P sao cho fi ( y)  0 với mọi i  N . Khi đó tồn tại hằng số   0 (chỉ phụ thuộc vào dữ kiện bài toán) sao cho dist ( x, P)     f ( x)   trong đó f ( x)   f1 ( x),..., f m ( x)  . T  Ax  a  x  n , (1.25) 13 Chương 2 Chặn sai số cho đa thức lồi Trong chương này chúng ta sẽ trình bày về một số tính chất của đa thức lồi, chặn sai số cho đa thức lồi. Nội dung trong chương này chủ yếu được trích dẫn trong [10]. 2.1. Một số tính chất của đa thức lồi 2.1.1. Định nghĩa và một số kết quả Cho C  n là tập lồi đóng. Ta dùng bd  C  để kí hiệu biên của C. Với x  C , nón pháp tuyến của C tại x được xác định bởi NC  x  : z  n : zT ( y  x)  0y  C. Ta gọi NC1 ( x) : h  NC ( x) : h  1 để kí hiệu tất cả các véctơ đơn vị trong NC ( x). Nón lùi xa C  của C được định nghĩa bởi C  : d  n : x  td  C, t  0, x  C. Dễ thấy C  là một nón lồi. Với một hàm lồi  , bởi [9, Theorem 8.7], tất cả các tập mức khác rỗng dạng  x : ( x)  c , c  , có cùng nón lùi xa, gọi là nón lùi xa của  . Không mất tính tổng quát, ta dùng kí hiệu S để chỉ nón lùi xa của  . Giả sử E  S  (S ). Thế thì E là không gian con và được gọi là không gian hằng [9, p. 69] của  . Bổ đề 2.1.1 ([9, p. 69]). Không gian hằng E là không gian con lớn nhất chứa trong S mà thỏa mãn E  z  n : ( x   z )   ( x), x  n ,   .