Tìm khoảng cách ngắn nhất từ 1 điểm đến 1 đường cong cho trước!

Sở dĩ tui hỏi bạn lập trình ngôn ngữ gì là vì hồi trước tui có viết thử phần tính đạo hàm theo symbol bằng Pascal. Thấy cũng có vẻ hơi phức tạp như bạn nói (tại vì tui viết dài & dở
-------------------------------------------
<BLOCKQUOTE id=quote><font size=1 face="Arial" id=quote>Trích từ: Còn về đạo hàm thì chỉ dùng máy tính được khi ta cần tính giá trị của đạo hàm tại 1 điểm nào đó, nhưng ở đây cái tôi cần là biểu thức đạo hàm của 1 hàm để giải hệ phương trình vi phân thì máy tính có vẻ như không giúp được. Chẳng hạn như dùng pp Newton bác có thể tính được Jacobian của hệ bằng ct f''''''''(x) = (f(x+dx) - f(x))/dx, nhưng lại gặp vấn đề khi bắt máy tính nó hiểu rằng đạo hàm của sin(x) là cos(x)... [/QUOTE]
=> bạn cho tui được thắc mắc 1 chút nghen: có thể tính đạo hàm bằng phương pháp số (gần đúng) mà vẫn giải được hệ phương trình vi phân hay không ? Thú thiệt tui không phải là dân toán => không biết giải (hệ) phương trình vi phân ra sao (Runge-Kutta ?). Nhưng tui xin lấy 1 ví dụ về giải phương trình phi tuyến (1 biến) bằng phương pháp lặp Newton:
Mình cần làm vòng lặp:
x = x - f(x)/derF(x);
Giả sử f(x) = sin(x); nếu mình tính được đạo hàm của f(x) chính xác (symbolic) thì mình đặt hàm derF(x) = cos(x)
Nhưng nếu mình chỉ tính được đạo hàm của f(x) theo phương pháp số (gần đúng) thì mình có thể đặt derF(x) = (f(x+dx) - f(x))/dx
=> mình vẫn tính được nghiệm gần đúng (nhưng sai số thì phức tạp hơn)
Như vậy có thể nào trong cách giải của bạn mỗi khi cần tính đạo hàm riêng: thay vì tìm biểu thức đạo hàm riêng chính xác bằng tay rồi thế các biến vô để tính giá trị, thì mình tính đạo hàm riêng bằng 1 phương pháp gần đúng nào đó ? (đằng nào thì mình cũng đang tìm kết quả cuối gần đúng trong 1 khoảng sai số nào đó)
(có gì sai sót xin các bạn chỉ giúp cho, cám ơn nhiều lắm)
-thân
[/QUOTE]
Bác nói đúng! Trong quá trình giải phương trình phi tuyến, thay vì xác định giá trị chính xác của hàm, ta hoàn toàn có thể xác định giá trị gần đúng của nó bằng 1 biểu thức đạo hàm. Khi đó ngoài việc khó khăn trong việc xác định sai số ra thì còn cả khó khăn trong việc chọn một step size để tính đạo hàm nữa, mà việc đó thì nó lại liên quan đến vấn đề round off.

Nói như bác thì đơn giản quá! Vấn đề là với một đường cong liên tục cho trước ta không thể băm nhỏ thành vô hạn số điểm trên đường cong đó, điều đó là phi thực tế.
Bác thích thực tế, em lấy cho bác một ví dụ: chẳng hạn em cần điều khiển 1 con robot bám theo một quỹ đạo cho trước, ví dụ hình sine, khi đó em sẽ phải điều khiển sao cho khoảng cách (gần nhất) từ robot đến đường cong tiến dần đến 0. Quỹ đạo (đường cong) này được tính toán bằng 1 thuật toán khác, ta không thể biết trước được, nó tuỳ thuộc vào địa hình. Ta cũng không thể biết được đường cong này kéo dài đến đâu để mà chia thành tập hợp điểm như bác nói. Vả lại với mỗi time-step em phải duyệt lại đống dữ liệu này từ đầu, dù cho bác có dùng binary search, thì cũng có thể khiến cho bộ nhớ overflow, về mặt thời gian thì highly unpredictable .
Được aivoges sửa chữa / chuyển vào 16:15 ngày 26/10/2004

Nếu vấn đề như bác aivoges nêu ra thì em sẽ làm bài toán như sau:
X n+1 = f( Xn )
Tức là tính toạ độ điểm tiếp theo như một hàm của toạ độ điểm hiện tại.

Thân gửi aigevos:

=> Như vậy trong ứng dụng thực tế, ngoài chuyện tìm ra lời giải, mình còn cần phảI xác định sai số, phải không aivoges ? Tui thắc mắc là có vẻ các công thức tính sai số trong chương trình đại học dựa trên giả thiết là mình có các hàm dưới dạng biểu thức chính xác (chứ không phải dùng phương pháp số để tính gần đúng giá trị tại 1 điểm bất kỳ) ? Nhưng tui nghĩ cho dù mình có các biểu thức chính xác, khi áp dụng computer để tính thì sẽ có sai số từ computer (ví dụ dấu chấm động của computer chỉ đúng tới n chữ số thập thân)
Tui không biết mình só thể tính sai đơn giản như sau không: nếu mình dùng 1 phương pháp lặp (và hội tụ) nào đó để tính x chẳng hạn thì:
sai_số_ở_bước_n <= | x_ở_bước_n - x_ở_bước_n_trừ_1 |
(nếu x là vector trong không gian k chiều thì xài khoảng cách giừa 2 điểm x_ở_bước_n và x_ở_bước_n_trừ_1)
???
-thân

=> Như vậy trong ứng dụng thực tế, ngoài chuyện tìm ra lời giải, mình còn cần phảI xác định sai số, phải không aivoges ? Tui thắc mắc là có vẻ các công thức tính sai số trong chương trình đại học dựa trên giả thiết là mình có các hàm dưới dạng biểu thức chính xác (chứ không phải dùng phương pháp số để tính gần đúng giá trị tại 1 điểm bất kỳ) ? Nhưng tui nghĩ cho dù mình có các biểu thức chính xác, khi áp dụng computer để tính thì sẽ có sai số từ computer (ví dụ dấu chấm động của computer chỉ đúng tới n chữ số thập thân)
Tui không biết mình só thể tính sai đơn giản như sau không: nếu mình dùng 1 phương pháp lặp (và hội tụ) nào đó để tính x chẳng hạn thì:
sai_số_ở_bước_n <= | x_ở_bước_n - x_ở_bước_n_trừ_1 |
(nếu x là vector trong không gian k chiều thì xài khoảng cách giừa 2 điểm x_ở_bước_n và x_ở_bước_n_trừ_1)
???
-thân
[/QUOTE]
Không được bạn mến ạ! Vì sai số ở đây là sai số tích luỹ (cumulative error). Ngay bản thân x_ở_bước_n và x_ở_bước_n_trừ_1 cũng bao gồm cả sai số của chính nó rồi.

Kính Gửi các Bác!
Các Bác đang giải quyết bài toán ?oDẫn đường cho Robot?, nếu vậy cần chú ý khi lập trình máy tính số ?ogiải các bài toán ứng dụng? là ta đang tìm nghiệm bằng ?oPhương pháp Tính Gần đúng?, thực hiện việc thay thế quá trình biến đổi liên tục bằng quá trình gián đoạn (cho phép có những bước nhẩy). Giả thuyết rằng những bước nhẩy nhỏ dần và nhỏ dần, còn tần số xuất hiện của chúng lại tăng dần, chúng ta hy vọng rằng nghiệm của ta đối với bài toán gián đoạn sẽ tiến dần đến nghiệm của bài toán liên tục. Thường là như vậy nhưng không phải bao giờ cũng như thế, bản thân ?oPhương pháp Tính Gần đúng? sẽ phát sinh của ?oSai số tích lũy?, do vậy khi lập trình cần chú ý ?oSai số và Sai số cho phép? của ứng dụng và tính ổn định của hệ.(1)
Có thể giải quyết bài toán ?oDẫn đường cho Robot? bằng phương pháp ?oSữ dụng Mạng Nơron Mờ Điều khiển Thích nghi Phi tuyến? trong thời gian thực.(2)
Mỗi người thường có cách riêng cho từng loại ứng dụng, tôi thường sữ dụng MATHCAD sau đó dịch sang một ngôn ngữ tiện dụng khác.
Tối hôm qua xem tin tức ?oHạn hán? trên VTV1, tôi mới hiểu ý nghĩa thực tiển của câu hỏi ?oMô phỏng Fuzzy Logic trong MatLab? và hôm nay là ?oDẫn đường cho Robot?; trong một chừng mực nào đó, nếu được trang bị mạnh về lý thuyết toán chuyên ngành thì giải một bài toán ứng dụng không phải là quá khó; cái khó là không biết xã hội Việt Nam hiện nay cần cái gì? Và bỏ lý thuyết liệu có ổn hay không? Học sinh miền nam trước 1975 để không phải đi Quân dịch thì sáng, chiều, tối và cả những ngày hè đều tự nguyện đi học, không ma nào ép và cũng không ai dám rên, không biết còn ai nhớ điều nầy không?
Ước gì tri thức là một cái ?obánh bao? hay một gói ?oMỳ ăn liền? thì "đi tắt đón đầu" mới là điều có thể tin được; Ngược lại xuất xưỡng một lô KS, ThS, TS giấy thì đây đúng là điều cần quan tâm suy nghiệm!!!
THÂN!
Tài liệu tham khảo:
1.-Lý thuyết ?oPhương pháp Tính? dể hiểu xem ?oNgôn ngữ BASIC dùng cho máy tính APPLE II? của Đàm Tuấn Hiệp, NXB-GTVT 1985.
2.-?oHệ Mờ và Ứng Dụng?, NXB-KHKT 1998; ?oLý thuyết Điều khiển Tuyến tính?, NXB-KHKT 2002.